题目描述

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

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

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

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

给定下降幂多项式 $f(x)$ 的系数 $a_n,a_{n-1},\cdots,a_0$ 与一个值 $m$，请计算 $f(m) \bmod 1,000,000,007$。

输入格式

• 第一行：两个整数 $n$ 与 $m$
• 第二行：$n+1$ 个整数 $a_n,a_{n-1},\cdots,a_1,a_0$

输出格式

• 单个整数：表示 $f(m) \bmod 1,000,000,007$。

数据范围

• $30\%$ 的数据，$1\leq n\leq 10$
• $60\%$ 的数据，$1\leq n\leq 5,000$
• $100\%$ 的数据，$1\leq n\leq 300,000$
• $-10^9\leq m\leq 10^9$
• $-10^9\leq a_i\leq 10^9$

样例数据

输入:

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