#include<bits/stdc++.h>
#define re return
#define ll long long
#define N 2000011
using namespace std;
ll n,k,p;
struct Jack{
ll f[4][4];
Jack(){memset(f,0,sizeof(f));}
inline Jack operator (const Jack &b)const{
Jack ans;
int i,j,k;
for(k=1;k<=3;++k)
for(i=1;i<=3;++i)
for(j=1;j<=3;++j)
ans.f[i][j]=((ans.f[i][j]+f[i][k]b.f[k][j]%p)%p+p)%p;
re ans;
}
inline void one( ){
int i,j;
for(i=1;i<=3;++i)f[i][i]=1;
}
inline void pre_one( ){
f[1][1]=f[1][2]=f[2][1]=f[3][3]=1;
}
inline void pre_two( ){
pre_one( );
f[3][1]=-1;
}
inline void pre_three( ){
f[3][1]=f[3][3]=1;
}
};
inline Jack qui(Jack a,ll b){
Jack ans;
ans.one( );
while(!!b){
if(b&1)ans=ansa;
a=aa,b>>=1;
}
re ans;
}
inline void exgcd(ll a,ll b,ll &x,ll &y,ll &d){
if(!b){d=a,x=1,y=0;return;}
exgcd(b,a%b,y,x,d);
y-=a/bx;
}
inline ll getinv(ll a,ll p){
ll x,y,d;
exgcd(a,p,x,y,d);
if(d!=1)re -1;
re (x%p+p)%p;
}
ll f[N],len[N],tot,q[N],vis[N];
int main( ){
scanf("%lld%lld%lld",&n,&k,&p);
int i;
f[1]=f[2]=1;
if(n<=2){puts("1");re 0;}
for(i=3;i<=2e6;++i){
f[i]=(f[i-1]+f[i-2])%k;
if(f[i]==1&&!len[1])len[1]=i;
ll inv(getinv(f[i],k));
if(inv!=-1&&!len[inv])len[inv]=i;
}
ll now(1),t(0),l;
int flag(0);
while(1){
l=len[now];
q[++tot]=now,vis[now]=tot;
if(!l){
for(i=1;i<tot;++i)t+=len[q[i]];
flag=1;
break;
}
now=(nowf[l-1])%k;
if(!!vis[now]){
for(i=1;i<vis[now];++i)t+=len[q[i]];
break;
}
}
Jack a,tr1,tr2;
tr1.pre_one( ),tr2.pre_two( ),a.pre_three( );
if(n<=t){
--len[1],--n;
for(i=1;i<vis[now];++i)
if(n>=len[q[i]]){
a=aqui(tr1,len[q[i]]-1)tr2;
n-=len[q[i]];
}else{
printf("%lld\n",(aqui(tr1,n)).f[3][1]);
re 0;
}
}else{
--len[1];
n-=t;
for(i=1;i<vis[now];++i)a=aqui(tr1,len[q[i]]-1)tr2;
if(!!flag){
printf("%lld\n",(aqui(tr1,n)).f[3][1]);
re 0;
}else{
ll size(0);
Jack tr;
tr.one( );
for(i=vis[now];i<=tot;++i){
tr=trqui(tr1,len[q[i]]-1)tr2;
size+=len[q[i]];
}
a=aqui(tr,n/size);
n=n%size;
for(i=vis[now];i<=tot;++i)
if(n>=len[q[i]]){
a=aqui(tr1,len[q[i]]-1)*tr2;
n-=len[q[i]];
}else{
// puts("WORK");
}
