Background

Special for beginners, ^_^

Description

$x$ 的 $k$ 次下降幂定义为

$$x^{(k)}=(x)(x-1)(x-2)...(x-k+1)$$

$x$ 的下降幂多项式是由 $x$ 的一组下降幂及系数组成的算式：

$$f(x)=a_nx^{(n)}+a_{n-1}x^{(n-1)}+...+a_2x^{(2)}+a_1x^{(1)}+a_0 $$

给定下降幂多项式 $f(x)$ 的系数 $a_n,a _{n?1},...a_0$ 与一个值 $m$ ,请计算 $f(m) \bmod 1,000,000,007$

Format

Input

$\circ$ 第一行：两个整数 $n$ 与 $m$ 。

$\circ$ 第二行：$n+1$ 个整数 $a_n,a _{n-1},...,a_1,a_0$

Output

$\circ$ 单个整数：表示$f(m)\bmod1,000,000,007$。

Limitation

$\circ$ $40\%$ 的数据, $1\leq n \leq 10$

$\circ$ $60\%$ 的数据, $1\leq n \leq 3,000$

$\circ$ $100\%$ 的数据, $1\leq n \leq 3,000,000$ 。

$\circ$ $-10^9\leq m\leq10^{9}$ 。

$\circ$ $-10^9\leq a_i\leq10^{9}$ 。

Samples

3 5
4 3 2 1

311

说明:

$f(x)=4(x)(x-1)(x-2)+3(x)(x-1)+2(x)+1$

$f(5)=4(5)(4)(3)+3(5)(4)+2(5)+1=240+60+10+1$