rt，TLE on #6 #8

代码：

#include<bits/stdc++.h>

using namespace std;

#define int long long

int n,p;

map<int,int>mp;

int mul(int a,int b){
	int res=0;
	if(a<b) swap(a,b);
	while(b){
		if(b&1) res=(res+a)%p;
		a=(a*2)%p;
		b>>=1;
	}
	return res;
}

int f(int n){
	if(mp[n]) return mp[n];
	if(n%2){
		int qwq1=f(n/2);
		int qwq2=f(n/2+1);
		return mp[n]=(mul(qwq1,qwq1)+mul(qwq2,qwq2))%p;
	}
	int qaq=f(n/2);
	return mp[n]=mul((2*f(n/2-1)%p+qaq),qaq);
}

int qpow(int a,int b){
	if(b==0) return 1;
	if(b%2==0){
		int qwq=qpow(a,b/2);
		return mul(qwq,qwq);
	}
	return mul(a,qpow(a,b-1));
}

signed main(){
	scanf("%lld%lld",&n,&p);
	mp[1]=mp[2]=1;
	int ans=qpow((f(n+3)+p-n-2+p)%p,n+1);
	printf("%lld",ans);
	return 0;
}