rt，简单矩阵快速幂加速递推。不知道为什么再极限数据会炸。

代码：

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
unsigned long long n,mod,fp[20],lim[20];
struct Matrix{
	unsigned long long a[3][3];
	Matrix(){
		memset(a,0,sizeof a);
	}
}tran,ans;
Matrix operator *(Matrix u,Matrix v){
	Matrix w; 
	int i,j,k;
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			for(k=0;k<3;k++){
				w.a[i][j]=(w.a[i][j]+(u.a[i][k]%mod)*(v.a[k][j]%mod))%mod;
			}
		}
	}
	return w;
}
Matrix ksm(Matrix lol,long long _){
	if(_==1){
		return lol;
	}
	Matrix t=ksm(lol,_/2);
	t=t*t;
	if(_%2==0){
		return t;
	}
	else{
		return t*lol;
	}
}
signed main(){
	cin>>n>>mod;
	memset(tran.a,0,sizeof(tran.a));
	memset(ans.a,0,sizeof(ans.a));
	tran.a[0][1]=1;
	tran.a[0][2]=1;
	tran.a[1][0]=0;
	tran.a[1][1]=1;
	tran.a[1][2]=1;
	tran.a[2][0]=0;
	tran.a[2][1]=0;
	tran.a[2][2]=1;
	fp[0]=0,fp[1]=1,fp[2]=10,fp[3]=100,fp[4]=1000,fp[5]=10000,fp[6]=100000,fp[7]=1000000,fp[8]=10000000,fp[9]=100000000,fp[10]=1000000000,fp[11]=10000000000,fp[12]=100000000000,fp[13]=10000000000000,fp[14]=100000000000000,fp[15]=100000000000000,fp[16]=1000000000000000,fp[17]=10000000000000000,fp[18]=1000000000000000000,fp[19]=1000000000000000000;
	lim[0]=1; 
	for(int i=1;i<=18;i++){
		lim[i]=lim[i-1]*10;
		lim[0]=2;
	}
	ans.a[0][0]=1;
	ans.a[1][0]=1;
	ans.a[2][0]=1;
	for(int i=1;i<=18;i++){
		if(lim[i-1]<=n){
			tran.a[0][0]=fp[i+1]%mod;
			if(i<18&&lim[i]-1<=n){
				ans=ksm(tran,lim[i]-lim[i-1])*ans;
			}
			else if(lim[i]>n){
				ans=ksm(tran,n-lim[i-1]+1)*ans;
			}
		}
		else{
			break;
		}
	}
	cout<<ans.a[0][0]<<endl;
	return 0;
}