TLE求助

#include<bits/stdc++.h>
#define LL long long
LL n,m;
LL TEN[19]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
LL st[4]={0,1,0,0};
struct mat{
	LL M[4][4];
	void zero(){memset(M,0,sizeof(M));}
	void one()
	{
		memset(M,0,sizeof(M));
		for(int i=1;i<=3;++i)
			M[i][i]=1;
	}
	void init(int len)
	{
		memset(M,0,sizeof(M));
		for(int i=1;i<=3;++i)
			M[1][i]=1;
		for(int i=2;i<=3;++i)
			M[2][i]=1;
		M[3][3]=TEN[len]%m;
	}
	mat operator * (const mat &s)const{
		mat tmp;
		memset(tmp.M,0,sizeof(tmp.M));
		for(register int k=1;k<=3;++k)
		{
			for(register int i=1;i<=3;++i)
			{
				if(!M[i][k])
					continue;
				for(register int j=1;j<=3;++j)
				{
					tmp.M[i][j]+=M[i][k]*s.M[k][j]%m;
					tmp.M[i][j]%=m;
				}
			}
		}
		return tmp;
	}
}G;
mat power(mat SAM,LL x)
{
	mat res;
	res.one();
	while(x)
	{
		if(x&1)
			res=res*SAM;
		x>>=1;
		if(x)
			SAM=SAM*SAM;
	}
	return res;
}
inline void update()
{
	LL tmp1=0,tmp2=0,tmp3=0;
	for(register int i=1;i<=3;++i)
		tmp1=(tmp1+st[i]*G.M[i][1]%m)%m;
	for(register int i=1;i<=3;++i)
		tmp2=(tmp2+st[i]*G.M[i][2]%m)%m;
	for(register int i=1;i<=3;++i)
		tmp3=(tmp3+st[i]*G.M[i][3]%m)%m;
	st[1]=tmp1,st[2]=tmp2,st[3]=tmp3;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(register int i=1;TEN[i-1]<=n;++i)
	{
		LL T=TEN[i]>n?n-TEN[i-1]+1ll:TEN[i]-TEN[i-1];
		G.init(i);
		G=power(G,T);
		update();
	}
	printf("%lld",st[3]);
}