题目描述

在矩阵中， $a_{i,j} = a_{i-1,j} +a_{i,j-1}( i,j \neq 0)$。

已知 $a _ {0,1} = 233$，$a_{0,2} = 2333$，$a_{0,3} = 23333$...

输入：$a_{1,0},a_{2,0},\dots,a_{n,0}$，求 $a_{n,m} \bmod 10^7+7$ 。

输入格式

有多个测试用例，请处理直到 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}$ 模 $10^7+7$。

输入输出样例 #1

输入 #1

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

输出 #1

234
2799
72937