龟速乘+矩阵快速幂+快速幂求助

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<bitset>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define endl '\n'
#define re register

using namespace std;
const int N=1e5+1;
ll n,mod;
inline ll mul(ll a,ll b)
{
	ll num=0;
	while(b)
	{
		if(b&1) num=(num+a)%mod;
		a=a*2%mod;
		b>>=1; 
	}
	return num;
}
struct node
{
	ll n,m,a[3][3];
	node operator *(const node &b)const
	{	
		node ans;
		ans.n=n,ans.m=b.m;
		for(int i=1;i<=ans.n;++i)
		{
			for(int j=1;j<=ans.m;++j)
			{
				ans.a[i][j]=0;
				for(int k=1;k<=m;++k)
				{
					ans.a[i][j]=(ans.a[i][j]+(a[i][k]%mod)*(b.a[k][j]%mod))%mod;	
				}
			 } 
		}
		return ans; 
	}
};
ll fastpow(ll b)
{
	node res,cnt;
	res.n=res.m=cnt.n=cnt.m=2;
	cnt.a[1][2]=cnt.a[2][1]=cnt.a[2][2]=res.a[1][1]=res.a[1][2]=1;
	cnt.a[1][1]=res.a[2][1]=res.a[2][2]=0;
	while(b)
	{
		if(b&1) res=res*cnt;
		cnt=cnt*cnt; 
		b>>=1;
	}
	return res.a[1][1];
}
ll qpow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=mul(res,a);
		a=mul(a,a); 
		b>>=1;
	}
	return res;
}
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;	
}
inline void write(int x)
{
    if(x<0){putchar('-');x=-x;}
	if(x>9) write(x/10);
    putchar(x%10+'0');return ;
}

int main()
{
	n=read(),mod=read();++n;
	cout<<qpow(((fastpow(n+1)-n-1+mod)%mod+mod)%mod,n)%mod<<endl;
    return 0;
}