题解：
矩阵裸体。
#include<cstdio>
#include<cstring>
#include<cmath>
typedef long long ll;
ll n,mod;
struct Matrix{
ll a[][];
Matrix (){
memset(a,,sizeof(a));
}
inline void e(){
for(int i=;i<=;i++)
a[i][i]=;
}
friend Matrix operator *(Matrix x,Matrix y){
Matrix c;
for(int k=;k<=;k++)
for(int i=;i<=;i++)
for(int j=;j<=;j++){
c.a[i][j]+=x.a[i][k]*y.a[k][j];
if(c.a[i][j]>mod)
c.a[i][j]%=mod;
}
return c;
}
friend Matrix operator ^(Matrix a,ll b){
Matrix ans;ans.e();
while(b){
if(b&) ans=ans*a;
b>>=;
a=a*a;
}return ans;
}
inline void kmod(ll k){
for(int i=;i<=;i++)
for(int j=i;j<=;j++)
a[i][j]=;
a[][]=k%mod;
}
};
int main(){
scanf("%lld%lld",&n,&mod);
Matrix ans;
ans.a[][]=;
ans.a[][]=;
ans.a[][]=;
int i;ll j;
for(i=,j=;j*<=n;j*=,i++){
Matrix b;b.kmod(j*);
ans=(b^(j*-j))*ans;
}//printf("%lld\n",ans.a[1][1]);
Matrix b;b.kmod(j*);
if(n-j+>)
ans=(b^(n-j+))*ans;
printf("%lld\n",ans.a[][]);
}