#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+5;
int n,mod;
int qpow(int a,int b){
	int ans=1,base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return ans;
}
int fac[MAXN],inv[MAXN];
int c(int n,int m){
	if(n<m) return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void init(){
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%mod;
	inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++)
		inv[i]=inv[mod%i]*(mod-mod/i)%mod;
	for(int i=1;i<=n;i++)
		inv[i]=inv[i-1]*inv[i]%mod; 
}
int a[MAXN],m;
int calc(int n){
	do{
		a[++m]=n%mod;
		n/=mod;
	}while(n);
}
int f[MAXN][2][2];
void add(int &x,int y){
	x=(x+y)%mod;
}
int solve(){
	calc(n);
	f[0][0][0]=1;
	for(int d=0;d<60;d++){
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				if(!f[d][j][k]) continue;
				for(int i=0;i<9;i++){
					int x=i,y=(i*2+k)%10,z=a[d+1];
					if((!j&&x>z)||(j&&x>=z))
						add(f[d+1][1][(i*2+k)>=10],f[d][j][k]*c(z,y)%mod*c(y,x));
					else
						add(f[d+1][0][(i*2+k)>=10],f[d][j][k]*c(z,y)%mod*c(y,x));
				}
			}
		}
	}
	return f[60][0][0];
}
signed main(){
	cin>>n>>mod;
	init();
	cout<<(qpow(3,n)-solve()+mod)*qpow(2,mod-2)%mod;
	return 0;
}