给定一个多项式 $A(x) = a_0 + \dots + a_n x^n$，其系数为整数，以及一个整数 $m$。 考虑一个多元多项式 $D(x_1, \dots, x_m)$，定义为： $$D(x_1, \dots, x_m) = \prod_{i=1}^{m} A(x_i) \prod_{j=1}^{i-1} (x_i - x_j)$$ 令 $s$ 为 $D(x_1, \dots, x_m)$ 所有系数的平方和。求 $s$ 对 $10^9 + 7$ 取模的结果。

输入格式

输入的第一行包含两个整数 $n$ ($0 \le n \le 500$) 和 $m$ ($0 \le m \le 10^9$)。 第二行包含 $n+1$ 个整数 $a_0, \dots, a_n$ ($0 \le a_i < 10^9 + 7$)。 保证 $a_n \neq 0$ 且 $a_0 \neq 0$。

输出格式

输出一个整数，即 $s$ 对 $10^9 + 7$ 取模的值。

样例

样例输入 1

2 0
1 2 3

样例输出 1

1

样例输入 2

2 1
1 2 3

样例输出 2

14

样例输入 3

2 2
1 2 3

样例输出 3

264

说明

对于 $A(x) = 1 + 2x + 3x^2$ 且 $m = 2$，我们有： $$D(x_1, x_2) = -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$$ 注意，当 $m = 0$ 时 $D = 1$，当 $m = 1$ 时 $D(x_1) = 1 + 2x_1 + 3x_1^2$。