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 1
1
2 2
0 0
3 7
23 47 16

Sample Output

234
2799
72937


 

这题的思路依旧是矩阵加速。

下面为题意：

递推关系为a_i,j=a_i-1,j+a_i,j-1。其中a_0,1,a_0,2等i=0的数为2333…。j=0的数为题目所提供。

任意给一个i,j，求他模10000007后所得的值。

我们可以通过构造矩阵一列一列的求出每列的值。到第j列后求第i行的值即可。

2333……可以通过前一个数*10+3来获得。因此我们的初始矩阵可以加上10和3来运行。

构造的转换矩阵如下：

 

 

AC代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,m,arr[15],arrans[15],out1;
typedef struct mar{
    long long m[15][15];
    void Init(){
        memset(m,0,sizeof(m));
        for(int i=0;i<15;i++)
            m[i][i]=1;
    }
}Mart;
Mart Multi(Mart a,Mart b){
    Mart c;
    for(int i=0;i<n+2;i++)
        for(int j=0;j<n+2;j++){
            c.m[i][j]=0;
            for(int k=0;k<n+2;k++)
                c.m[i][j]+=(a.m[i][k]*b.m[k][j])%10000007;
            c.m[i][j]%=10000007;
        }
    return c;
}
Mart Quick_pow(Mart a,int m){
    Mart ans;
    ans.Init();
    while(m){
        if(m&1)
            ans=Multi(ans,a);
        m>>=1;
        a=Multi(a,a);
    }
    return ans;
}
int main(){
    while(~scanf("%lld%lld",&n,&m)){
        Mart transf;
        arr[0]=23,arr[n+1]=3;
        for(int i=1;i<=n;i++)
            scanf("%lld",&arr[i]);
        for(int i=0;i<n+2;i++)
            for(int j=0;j<n+2;j++){
                if(j==0&&i!=n+1)
                    transf.m[i][j]=10;
                else if((j==n+1)||(i>=j&&i!=n+1))
                    transf.m[i][j]=1;
                else
                    transf.m[i][j]=0;
            }
        Mart ans = Quick_pow(transf,m);
        out1=0;
        for(int i=0;i<n+2;i++)
            out1+=(ans.m[n][i]*arr[i])%10000007;
        out1%=10000007;
        printf("%lld\n",out1);
    }
    
}