struct Matrix{
    int val[N][N];

    Matrix(){
        memset(val, 0, sizeof(val));
    }

    friend Matrix operator * (const Matrix &A, const Matrix &B){
        Matrix C;
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= n; ++j){
                for (int k = 1; k <= n; ++k){
                    (C.val[i][j] += A.val[i][k] * B.val[k][j] % MOD);
                    if (C.val[i][j] >= MOD) C.val[i][j] -= MOD;
                }
            }
        }
        return C;
    }

    friend Matrix Pow(Matrix A, int nn){
        Matrix B;
        for (int i = 1; i <= n; ++i) B.val[i][i] = 1;
        while (nn > 0){
            if (nn & 1) B = B * A;
            A = A * A;
            nn >>= 1;
        }
        return B;
    }

    friend Matrix Pow(Matrix A, string s){
        Matrix B[10];
        Matrix C;
        for (int i = 1; i <= n; ++i) B[0].val[i][i] = C.val[i][i] = 1;
        for (int i = 1; i < 10; ++i) B[i] = B[i-1] * A;
        for (int i = 0; i < s.size(); ++i){
            C = Pow(C, 10);
            C = C * B[s[i] - '0'];
        }
        return C;
    }

};