If x < 10 f(x) = x.

If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);

And ai(0<=i<=9) can only be 0 or 1 .

Sample Input

10 9999

1 1 1 1 1 1 1 1 1 1

20 500

1 0 1 0 1 0 1 0 1 0

 

Sample Output

45

104

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 using namespace std; 6 int k,n; 7 struct Matrix 8 { 9     int mat[10][10];10 }p;11 int aa[10];12 Matrix mul(Matrix a,Matrix b)13 {14     Matrix c;15     for(int i=0;i<10;i++)16     {17         for(int j=0;j<10;j++)18         {19             c.mat[i][j]=0;20             for(int k=0;k<10;k++)21                 c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%n;22         }23     }24     return c;25 }26 Matrix mod_pow(Matrix x,int n)27 {28     Matrix res;29     memset(res.mat,0,sizeof(res.mat));30     for(int i=0;i<10;i++)31         res.mat[i][i]=1;32     while(n)33     {34         if(n&1)35             res=mul(res,x);36         x=mul(x,x);37         n>>=1;38     }39     return res;40 }41 int main()42 {43     freopen("in.txt","r",stdin);44     while(scanf("%d%d",&k,&n)!=EOF)45     {46         if(k<10)47         {48             printf("%d\n",k);49             continue;50         }51         memset(p.mat,0,sizeof(p.mat));52         for(int i=0;i<10;i++)53             cin>>p.mat[0][i];54         for(int i=1;i<10;i++)55             p.mat[i][i-1]=1;56         Matrix ans= mod_pow(p,k-9);57         /*for(int i=0;i<10;i++)58         {59             for(int j=0;j<10;j++)60                 cout<
           
            <<" ";61             cout<