2647. [POJ 5015]233矩阵

【题目描述】

在我们的日常生活中，我们经常使用 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\neq0$)$。

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

【输入格式】

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

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

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

【输出格式】

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

每个结果占一行。

【样例输入】

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

【样例输出】

234
2799
72937

【样例说明】

【数据规模与约定】

$1\leq n\leq 10,1\leq m\leq 10^9,0\leq a_{i,0}<2^{31}$。