rt，提交记录

#include<bits/stdc++.h>
#define int unsigned long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define fd(i,r,l) for(int i=r;i>=l;i--)
#define sqrt __builtin_sqrt
using namespace std;
int n,M,tmp=1,lst;
struct matrix{
	int n,m,a[15][15];
	void dbg(){
		fo(i,1,n){
			fo(j,1,m)cout<<a[i][j]<<' ';
			cout<<'\n';
		}
	}
	matrix(){memset(a,0,sizeof a);}
	matrix operator*(matrix shx){
		matrix ans;
		ans.n=n,ans.m=shx.m;
		fo(i,1,n)fo(j,1,shx.m)fo(k,1,m)(ans.a[i][j]+=(__int128)a[i][k]*(__int128)shx.a[k][j]%M)%=M;
		return ans;
	}
};
matrix qp(matrix x,int p){
	matrix ans;
	ans.n=ans.m=3;
	fo(i,1,3)ans.a[i][i]=1;
	while(p){
		if(p&1)ans=ans*x;
		x=x*x,p>>=1;
	}
	return ans;
}
int pww(int x){int tmp=1;fo(i,1,x)tmp*=10;return tmp;}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>M;
	fo(i,1,(int)log10(n)){
		matrix a,b;
		a.n=a.m=b.n=3,
		b.m=a.a[1][2]=a.a[1][3]=a.a[2][2]=a.a[2][3]=a.a[3][3]=b.a[3][1]=1,
		a.a[1][1]=tmp=tmp*10%M,
		b.a[2][1]=((int)pww(i-1)%M-1+M)%M,
		b.a[1][1]=lst;
		if(i<(int)log10(n)){
			matrix ans=qp(a,pww(i)-pww(i-1))*b;
			lst=ans.a[1][1];
		}
		else{
			matrix ans=qp(a,n+1-pww(i-1))*b;
			cout<<ans.a[1][1]%M;
		}
	}
	return 0;
}