#P18161. Sum of Squares

Sum of Squares

Sum of Squares

给定一个整系数多项式

A(x)=a0+a1x+⋯+anxnA(x)=a_0+a_1x+\dots+a_nx^n

和一个整数 mm。定义多元多项式

$$D(x_1,\dots,x_m)=\prod_{i=1}^{m}A(x_i)\prod_{1\le j<i\le m}(x_i-x_j).$$

设 ss 为 DD 的所有系数(按单项式展开后)的平方和。求 s mod (109+7)s\bmod (10^9+7)。

输入格式

第一行两个整数 n,mn,m(0≤n≤5000\le n\le500,0≤m≤1090\le m\le10^9)。

第二行 n+1n+1 个整数 a0,a1,…,ana_0,a_1,\dots,a_n(0≤ai<109+70\le a_i<10^9+7)。

保证 an≠0a_n\ne0,a0≠0a_0\ne0。

输出格式

输出一个整数,表示 s mod (109+7)s\bmod(10^9+7)。

样例 1

输入:

2 0
1 2 3

输出:

1

样例 2

输入:

2 1
1 2 3

输出:

14

样例 3

输入:

2 2
1 2 3

输出:

264

空乘积按1处理,所以m=0时D=1。m=1时D(x₁)=1+2x₁+3x₁²,系数平方和为14。m=2时

$$\begin{aligned} D={}&-9x_1^3x_2^2-6x_1^3x_2-3x_1^3 +9x_1^2x_2^3-x_1^2x_2-2x_1^2\\ &+6x_1x_2^3+x_1x_2^2-x_1 +3x_2^3+2x_2^2+x_2, \end{aligned}$$

合并相同单项式后再求系数平方和,结果为264。