龟速乘做法TLE3点？

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL N,P;
inline LL mul(LL a,LL b){
	LL 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;
}
struct matrix{
	LL a[4][4];
	matrix(){memset(a,0,sizeof(a));}
	matrix operator *(matrix &b){
		matrix res;
		for(register int i=1;i<=2;i++)
			for(register int j=1;j<=2;j++)
				for(register int k=1;k<=2;k++)
					res.a[i][j]=(res.a[i][j]+mul(a[i][k],b.a[k][j]))%P;
		return res;
	}
}base,res,ans;
void quickpow(LL b){
	while(b){
		if(b&1) res=base*res;
		base=base*base;
		b>>=1;
	}
}
void init(){
	ans.a[1][1]=ans.a[2][1]=1;
	res.a[1][1]=res.a[2][2]=1;
	base.a[1][1]=base.a[1][2]=base.a[2][1]=1;
}
LL qp(LL a,LL b){
	LL res=1;
	while(b){
		if(b&1) res=mul(a,res);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
int main(){
	scanf("%lld%lld",&N,&P);
	init();
	quickpow(N+1);
	ans=res*ans;
	printf("%lld\n",qp((ans.a[1][1]-N-2+P)%P,N+1)%P);
	return 0;
}