记录编号	577252	评测结果	AAAAAAAAAA
题目名称	[AHOI 2004] 数字迷阵	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-10-28 22:51:25	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3000+5;
ll x,y,mod;
ll f[N];
int cnt=3,p[N],d=0;
struct sdf{
	ll m[5][5];
	sdf operator*(const sdf&x)const{
		sdf tmp;
		tmp.m[1][1]=tmp.m[1][2]=tmp.m[2][1]=tmp.m[2][2]=0;
		for (int i=1;i<=2;i++){
			for (int j=1;j<=2;j++){
				for (int k=1;k<=2;k++)tmp.m[i][j]=(tmp.m[i][j]+m[i][k]*x.m[k][j]%mod)%mod;
			}
		}
		return tmp;
	}
}g,q;
void fst(ll x){
	if (x==1)return ;
	if (x&1){
		fst(x-1);g=g*q;
	}
	else{
		fst(x/2);g=g*g;
	}
	return ;
}
ll fib(ll k){
	if (k==1)return 1;
	g=q;
	fst(k-1);
	return (g.m[1][1]+g.m[2][1])%mod;
}
int main(){
	freopen ("nummaze.in","r",stdin);
	freopen ("nummaze.out","w",stdout);
	scanf("%lld%lld%lld",&x,&y,&mod);
	q.m[1][1]=q.m[1][2]=q.m[2][1]=1;
	f[1]=1;f[2]=2;
	for (;;cnt++){
		f[cnt]=f[cnt-1]+f[cnt-2];
		if (f[cnt]>=x)break;
	}
	ll t=x-1,ans=fib(y)%mod;
	for (int i=cnt;i>=1;i--){
		if (f[i]<=t){
			t-=f[i];ans=(ans+fib(y+i+1))%mod;
		}
	}
	printf("%lld\n",ans%mod);
	return 0;
}