E. Sum of Squares
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a polynomial $$$A(x) = a_0 + \dots + a_n x^n$$$ with integer coefficients and an integer $$$m$$$.

Consider a multivariate polynomial $$$D(x_1,\dots,x_m)$$$, defined as $$$$$$ D(x_1,\dots,x_m) = \prod\limits_{i=1}^m A(x_i) \prod\limits_{j=1}^{i-1} (x_i - x_j). $$$$$$

Let $$$s$$$ be the sum of squares of all coefficients of $$$D(x_1,\dots,x_m)$$$. Find $$$s$$$ modulo $$$10^9+7$$$.

Input

The only line of input contains two integers $$$n$$$ ($$$0 \leq n \leq 500$$$) and $$$m$$$ ($$$0 \leq m \leq 10^9$$$).

The second line contains $$$n+1$$$ integers $$$a_0,\dots,a_{n}$$$ ($$$0 \leq a_i \lt 10^9+7$$$).

It is guaranteed that $$$a_n \neq 0$$$ and $$$a_0 \neq 0$$$.

Output

Print a single integer, the value of $$$s$$$ modulo $$$10^9+7$$$.

Examples
Input
2 0
1 2 3
Output
1
Input
2 1
1 2 3
Output
14
Input
2 2
1 2 3
Output
264
Note

For $$$A(x) = 1 + 2x + 3x^2$$$ and $$$m = 2$$$, we have $$$$$$ D(x_1, x_2) = - 9 x_{1}^{3} x_{2}^{2} - 6 x_{1}^{3} x_{2} - 3 x_{1}^{3} + 9 x_{1}^{2} x_{2}^{3} - x_{1}^{2} x_{2} - 2 x_{1}^{2} + 6 x_{1} x_{2}^{3} + x_{1} x_{2}^{2} - x_{1} + 3 x_{2}^{3} + 2 x_{2}^{2} + x_{2}. $$$$$$

Note that also $$$D = 1$$$ for $$$m = 0$$$ and $$$D(x_1) = 1 + 2x_1 + 3x_1^2$$$ for $$$m = 1$$$.