题目描述

$x$ 的 $k$ 次升幂定义为：

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

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

$$f(x)=a_0+a_1\times x^{(1)}+a_2\times x^{(2)}+\cdots+a_n\times x^{(n)}.$$

现在给定系数 $a_0,a_1,\ldots,a_n$ 与参数 $x$，计算 $f(x)$ 除以 $10^9+7$ 的非负余数。

输入格式

第一行两个整数 $n,x$；第二行 $n+1$ 个整数 $a_0,a_1,\ldots,a_n$。

输出格式

一行一个整数，表示计算结果。

样例 1

输入

3 2
1 2 3 4

输出

119

样例 2

输入

9 5
7 5 9 5 5 8 5 1 1 5

输出

319804305

样例 3

输入

7 5
-4 8 4 -2 4 6 -1 -9

输出

984977183

说明

样例 1：$f(2)=1+2\times2+3\times2\times3+4\times2\times3\times4=119$。

数据范围

70% 的数据：$1\le n\le5000$。全部数据：$1\le n\le5\times10^5$，$-10^9\le x,a_i\le10^9$。