题目描述

在我们的日常生活中，我们经常使用 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 1
1
2 2
0 0
3 7
23 47 16

234
2799
72937

样例解释：

数据范围

$1≤n≤10;1≤m≤10^9;0≤a_{i,0}<2^{31}$

来源

• HDU5015
• 算法竞赛进阶指南