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

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

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

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

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

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

输入格式

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

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

第二行包含 $n$ 个整数，表示 $a\_{1,0},a\_{2,0},…,a\_{n,0}$。

输出格式

每组数据输出一个整数，表示 $a\_{n,m} \bmod 10000007$ 的值。

每个结果占一行。

数据范围

$1 \le n \le 10$,

$1 \le m \le 10^9$,

$0 \le a\_{i,0} < 2^{31}$

样例解释：

Samples

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

234
2799
72937