思路就是矩阵乘法优化DP，开了unsigned long long，但是还是WA

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=29;
int n,MOD,pow10[N];
class Matrix{
	public:
		int r,c,data[N][N];
		Matrix(int rr,int cc){
			r=rr; c=cc;
			memset(data,0,sizeof(data));
		}
		Matrix operator*(const Matrix&m)const{
			Matrix ans(r,m.c);
			for(int i=0;i<=r-1;i++){
				for(int j=0;j<=m.c-1;j++){
					for(int k=0;k<=c-1;k++){
						ans.data[i][j]+=((data[i][k]%MOD)*(m.data[k][j]%MOD))%MOD;
						ans.data[i][j]%=MOD;
					}
				}
			}
			return ans;
		}
		Matrix operator^(int p)const{
			Matrix ans(r,c);
			for(int i=0;i<=r-1;i++) ans.data[i][i]=1;
			Matrix x=*this;
			while(p!=0){
				if(p%2==1) ans=ans*x;
				x=x*x; p/=2;
			}
			return ans;
		}
};
int countdigit(int k){
	int cnt=0;
	do{
		cnt++;
		k/=10;
	}while(k!=0);
	return cnt;
}
signed main(){
	cin>>n>>MOD;
	int bound=countdigit(n);
	pow10[0]=1; for(int i=1;i<=18;i++) pow10[i]=(pow10[i-1]*10)%MOD;
	Matrix ans(3,1);
	ans.data[0][0]=0;
	ans.data[1][0]=0;
	ans.data[2][0]=1;
	for(int digit=1;digit<=bound-1;digit++){
		Matrix p(3,3);
		p.data[0][0]=pow10[digit]; p.data[0][1]=1; p.data[0][2]=1;
		p.data[1][0]=0; p.data[1][1]=1; p.data[1][2]=1;
		p.data[2][0]=0; p.data[2][1]=0; p.data[2][2]=1;
		p=p^(pow10[digit]-pow10[digit-1]);
		ans=p*ans;
	}
	Matrix p(3,3);
	p.data[0][0]=pow10[bound]; p.data[0][1]=1; p.data[0][2]=1;
	p.data[1][0]=0; p.data[1][1]=1; p.data[1][2]=1;
	p.data[2][0]=0; p.data[2][1]=0; p.data[2][2]=1;
	p=p^(n-pow10[bound-1]+1);
	ans=p*ans;
	cout<<ans.data[0][0];
	return 0;
}