斐波那契，简单；题，难

#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=ans*a;
		a=a*a,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/b*x;
}
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=(now*f[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=a*qui(tr1,len[q[i]]-1)*tr2;
			n-=len[q[i]];
		}else{
			printf("%lld\n",(a*qui(tr1,n)).f[3][1]);
			re 0;
		}
	}else{
		--len[1];
		n-=t;
		for(i=1;i<vis[now];++i)a=a*qui(tr1,len[q[i]]-1)*tr2;
		if(!!flag){
			printf("%lld\n",(a*qui(tr1,n)).f[3][1]);
			re 0;
		}else{
			ll size(0);
			Jack tr;
			tr.one( );
			for(i=vis[now];i<=tot;++i){
				tr=tr*qui(tr1,len[q[i]]-1)*tr2;
				size+=len[q[i]];
			}
			a=a*qui(tr,n/size);
			n=n%size;
			for(i=vis[now];i<=tot;++i)
			if(n>=len[q[i]]){
				a=a*qui(tr1,len[q[i]]-1)*tr2;
				n-=len[q[i]];
			}else{
				
				printf("%lld\n",(a*qui(tr1,n)).f[3][1]);
				re 0;
			}
		}
	}

}