这个是矩阵乘法

#include<iostream>
#include<cstring>

#define N 3

#define MOD m

#define ll long long

using namespace std;

struct matrix{

    ll a[N][N];

    matrix(){memset(a,0,sizeof(a));}

}c,ans;

int n,m,tmp;

int t[20];

matrix operator *(const matrix &x,const matrix &y){

    matrix z;

    for(int i=0;i<N;i++) for(int j=0;j<N;j++) for(int k=0;k<N;k++){

        z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;

    }

    return z;

}

template <typename T>

T ksm(T a, long long b){

    T res=a; b--;

    while(b){

        if(b & 1) res=res *a;

        a=a*a;

        b>>=1;

    }

    return res;

}

int main(){

    int i;

    cin>>n>>m;

    ans.a[0][1] = ans.a[0][2] = c.a[1][0] = c.a[1][1] = c.a[2][1] = c.a[2][2] = 1;

    for (i = 1,t[0]=1; i <= 18; i++) t[i] = t[i - 1] * 10;

    for (i = 1;; i++) {

        c.a[0][0] = t[i] % m;

        tmp = min(n, t[i] - 1) - t[i - 1] + 1;

        ans = ans * ksm(c, tmp);

        if (t[i] - 1 >= n) break;

    }

    cout << ans.a[0][0] << endl;

    return 0;

}