rt，不太会卡常，代码很垃圾大佬轻喷

#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace matrix{
	vector<vector<int>> mul(vector<vector<int>> a,vector<vector<int>> b,int mod){
		int n=a.size();
		vector<vector<int>> ans(n,vector<int>(n,0));
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				for(int k=0;k<n;k++){
					ans[i][j]=(ans[i][j]+(a[i][k]*b[k][j]))%mod;
				}
			}
		}
		return ans;
	}
	vector<vector<int>> qpow(vector<vector<int>> a,int b,int mod){
		if(b==1) return a;
		vector<vector<int>> ans=matrix::qpow(a,b/2,mod);
		ans=matrix::mul(ans,ans,mod);
		if(b%2==1) ans=matrix::mul(ans,a,mod);
		return ans;
	}
}
const int mod=1e9+7;
signed main(){
    vector<vector<int>> f(2,vector<int>(2,0));
	f[0][0]=1;f[0][1]=1;f[1][0]=1;f[1][1]=0;
    int t,p,n;cin>>t;
	while(t--){
	    cin>>n>>p;
	    if(n==1){cout<<"2\n";continue;}
	    vector<vector<int>> ans=matrix::qpow(f,n-1,p);
	    int fn1=(ans[0][0]+ans[0][1]);
	    int fn=(ans[1][0]+ans[1][1]);
	    cout<<((fn*fn%p*fn1%p)+(fn*fn1%p))%p<<endl;
	}
    return 0;
}

状态：TLE 1,3,4,6