rt，不知道是时间复杂度假了还是常数大了

#include<bits/stdc++.h>
#define int long long
using namespace std;
char *p1,*p2,buf[1000100];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000096,stdin),p1==p2)?EOF:*p1++)
int read(){
    int x=0;char c=gc();
    while(c<48)c=gc();
    while(c>47)x=(x<<3)+(x<<1)+(c&15),c=gc();
    return x;
}
const int N=500100;
int mod;
struct M{
    int n,m,z[3][3];
    M() {n=m=0;memset(z,0,sizeof z);}
} ;
M operator*(const M&l,const M&r){
    M res;
    res.n=l.n,res.m=r.m;
    for(int k=1;k<3;++k)
    for(int i=1;i<3;++i)
    for(int j=1;j<3;++j)
    res.z[i][j]=(res.z[i][j]+l.z[i][k]*r.z[k][j]%mod)%mod;
    return res;
}
M ksm(M a,int b){
    M E;E.n=E.m=2;
    E.z[1][1]=E.z[2][2]=1;
    while(b){
        if(b&1)E=E*a;
        a=a*a,b>>=1;
    }
    return E;
}
int fibo(int x){
    if(!x)return 0;if(x<=2)return 1;
    M st,bas;st.n=st.m=bas.m=2;bas.n=1;
    st.z[1][1]=st.z[1][2]=st.z[2][1]=bas.z[1][1]=bas.z[1][2]=1;
    return (bas*ksm(st,x-1)).z[1][2];
}
signed main(){
    int T=read();
    while(T--){
        int n=read();mod=read();
        int f1=fibo(n),f2=fibo(n+1);
        printf("%lld\n",f1*f2%mod*(1+f1)%mod);
    }
    return 0;
}