#include<stdio.h>
long long a11,a12,a21,a22,b11,b12,b21,b22,p11,p12,p21,p22,k,m=666013;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%lld%lld",&k,&m);
}
void solve()
{
	p11=1;p12=1;
	p21=1;p22=0;
	a11=1;a12=0;
	a21=0;a22=1;
	while(k)
	{
		if(k%2==1)
		{
			b11=(a11*p11+a12*p21)%m;
			b12=(a11*p12+a12*p22)%m;
			b21=(a21*p11+a22*p21)%m;
			b22=(a21*p12+a22*p22)%m;
			a11=b11;a12=b12;a21=b21;a22=b22;
		}
		b11=(p11*p11+p12*p21)%m;
		b12=(p11*p12+p12*p22)%m;
		b21=(p21*p11+p22*p21)%m;
		b22=(p21*p12+p22*p22)%m;
		p11=b11;p12=b12;p21=b21;p22=b22;
		k/=2;
	}
	printf("%lld\n",a12);			
}