说明

在我们的日常生活中，我们经常使用233来表达我们的感受。

实际上，我们可能会说2333,23333或233333 ......意思相同。

假设我们有一个名为233矩阵的矩阵。

在第一行，它将包含233,2333,23333 …（这意味着$\red{a_{0,1} = 233}$，$\red{a_{0,2} = 2333}$，$\red{a_{0,3} = 23333}$ … ）。

此外，在233矩阵中，满足$\red{a_{i,j} = a_{i−1,j} + a_{i,j−1}}$ （$\red{i,j≠0}$）。

现在给定$\red{a_{1,0} , a_{2,0} , }$......$\red{, a_{n,0}}$，请求出在233矩阵中$\red{a_{n,m} }$的值。

输入格式

输入包含多组数据，请处理至文件末尾。

每组数据包括两行，第一行包含两个整数$\red{n，m}$。

第二行包含$\red{n}$个整数，表示$\red{a_{1,0} , a_{2,0} , }$......$\red{, a_{n,0} }$。

输出格式

每组数据输出一个整数，表示$\red{a_{n,m} mod 10000007}$的值。

每个结果占一行。

样例

输入样例

1 1
1
2 2
0 0
3 7
23 47 16

输出样例

234
2799
72937

提示

$\red{1 ≤ n ≤ 10}$,

$\red{1 ≤ m ≤ 10^9}$,

$\red{0 ≤ a_{i,0} < 2^{31} }$

$样例解释:$

$Case \#\red 1$:

$$\red{ \begin{pmatrix} 0 & 233 & \\ 1 & 234 & \\ \end{pmatrix} } $$

$Case \#\red 2$:

$$\red{ \begin{pmatrix} 0 & 233 & 2333 & \\ 0 & 233 & 2566 & \\ 0 & 233 & 2799 &\\ \end{pmatrix} } $$