题目描述

在我们的日常生活中，我们经常用 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 \neq 0)$。现在已知 $a_{1,0},a_{2,0},\dots,a_{n,0}$，你能告诉我 233 矩阵中的 $a_{n,m}$ 吗？

输入格式

有多个测试用例，请处理直到 EOF。

对于每个案例，第一行包含两个正整数 $n,m(n \le 10,m \le 10^9)$。第二行包含 n 个整数，$a_{1,0},a_{2,0},...,a_{n,0}$（$0 \le a_i,0 < 2^{31}$）。

输出格式

对于每个案例，输出 $a_{n,m}$ 模 10000007。

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

234
2799
72937

提示