Problem Description

Lele now is thinking about a simple function f(x).

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 .

Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.

 

Input

The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.

 

Output

For each case, output f(k) % m in one line.

 

Sample Input

 

Sample Output

 

Author

linle

 

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#define LL long long

using namespace std;

const int N = ;

int Mod, K;

struct mat

{

    int m[][];

}base, tmp, ans;

mat muti(mat a, mat b)

{

    mat res;

    memset(res.m, , sizeof(res.m));

    for(int i = ; i <= N; i++)

    for(int j = ; j <= N; j++){

        if(a.m[i][j]){

            for(int k = ; k <= N; k++){

                res.m[i][k] = (res.m[i][k] + a.m[i][j] * b.m[j][k])%Mod;

            }

        }

    }

    return res;

}

mat qpow(mat a, int n)

{

    mat res;

    memset(res.m, , sizeof(res.m));

    for(int i = ; i <= N; i++) res.m[i][i] = 1LL;

    while(n){

        if(n&){

            res = muti(res, a);

        }

        a = muti(a, a);

        n>>=;

    }

    return res;

}

int main()

{

    while(~scanf("%d%d", &K, &Mod)){

        memset(base.m, , sizeof(base.m));

        for(int i = ; i < ; i++){

            base.m[i][] = i;

        }

        memset(tmp.m, , sizeof(tmp.m));

        for(int i = ; i <= ; i++){

            tmp.m[i][i+] = ;

        }

        for(int i = ; i >= ; i--){

            scanf("%d", &tmp.m[][i]);         //构造递推关系矩阵

            base.m[][] += ((LL)(i-)*tmp.m[][i])%Mod;

        }

        //see see

//            for(int i = 1; i <= 10; i++){

//                for(int j = 1; j <= 10; j++){

//                    printf("%d ", tmp.m[i][j]);

//                }

//                puts("");

//            }

        if(K <= ){

            printf("%d\n", base.m[K][]);

        }

        else{

            tmp = qpow(tmp, K-);

            ans = muti(tmp, base);

//            //see see

//            for(int i = 1; i <= 10; i++){

//                for(int j = 1; j <= 10; j++){

//                    printf("%d ", tmp.m[i][j]);

//                }

//                puts("");

//            }

            printf("%d\n", ans.m[][]%Mod);

        }

    }

    return ;

}