rt,WA on #6,7,8,10

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N=5;
ll n,mod;

struct mult{
	ll a[N][N];
	mult() { memset(a,0,sizeof(a)); }
	mult operator * (const mult &b) const
	{
		mult c;
		for(int k=0;k<N;k++)
		{
			for(int i=0;i<N;i++)
			{
				ll r=a[i][k];
				for(int j=0;j<N;j++)
					c.a[i][j]=(c.a[i][j]+1ll*r%mod*b.a[k][j]%mod)%mod;
			}
		}
		return c;
	}
};

mult qpow(mult x,ll y)
{
	mult res;
	for(int i=1;i<=3;i++)
		res.a[i][i]=1;
	for(;y;y>>=1)
	{
		if(y&1) res=res*x;
		x=x*x;
	}
	return res;
}
mult x,base;

void init()
{
	for(int i=1;i<=3;i++) x.a[1][i]=1;
	for(int i=1;i<=2;i++)
		base.a[2][i]=base.a[3][i]=1;
	base.a[1][1]=base.a[3][3]=1;
	return ;
}

int main()
{
	cin>>n>>mod;
	init();
	ll now=1;
	while(1)
	{
		base.a[1][1]*=10;
		ll t=base.a[1][1]-1;
		if(t>=n) t=n;
		x=x*qpow(base,t-now);
		if(t==n) break;
		now=t;
	}
	cout<<x.a[1][1];
	return 0;
}