In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 ... in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333... (it means a 

_0,1 = 233,a 

_0,2 = 2333,a 

_0,3 = 23333...) Besides, in 233 matrix, we got a

_i,j = a 

_i-1,j +a 

_i,j-1( i,j ≠ 0). Now you have known a 

_1,0,a 

_2,0,...,a 

_n,0, could you tell me a 

_n,m in the 233 matrix?

InputThere are multiple test cases. Please process till EOF. 

For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 10 ⁹). The second line contains n integers, a _1,0,a _2,0,...,a _n,0(0 ≤ a _i,0 < 2 ³¹).OutputFor each case, output a _n,m mod 10000007.Sample Input

1 112 20 03 723 47 16

Sample Output

234279972937

Hint

 

矩阵快速幂

比较裸 ，首先找到原态和现态的关系，233，2333，23333，23333， 这些数都遵循 a0=a0'*10+3  ，

a1=a0'*10+3+a1'  ;   a2=a0'*10+3+a1'+a2'  ;  a3=a0'*10+3+a1'+a2'+a3'  ;

即 an=a0'*10+3+

 

代码如下：

#include
      
       #include
       
        #include
        
         const int MOD=10000007;using namespace std;typedef long long LL;const int M=15;struct Matrix{    LL matrix[M][M];};int n;//矩阵的阶数void init(Matrix &res){    for(int i=0;i<=n;i++)    {        for(int j=0;j<=n;j++)            res.matrix[i][j]=0;        res.matrix[i][i]=1;    }}Matrix multiplicative(Matrix a,Matrix b){    Matrix res;    memset(res.matrix,0,sizeof(res.matrix));    for(int i = 0 ; i < n ; i++)        for(int j = 0 ; j < n ; j++)            for(int k = 0 ; k < n ; k++)                res.matrix[i][j] =(res.matrix[i][j]%MOD+a.matrix[i][k]%MOD*b.matrix[k][j]%MOD)%MOD;return res;}Matrix pow(Matrix mx,int m){    Matrix res,base=mx;    init(res); //初始为单位矩阵，即除主对角线都是1外，其他都是0    while(m)    {        if(m&1)            res=multiplicative(res,base);        base=multiplicative(base,base);        m>>=1;    }    return res;}void lk_init(Matrix &b){    for(int i=0;i