本文中 $fib$ 表示 Fibonacci 数列。

显然可以把乘法转换成加法，题目等价于求 $p^{fib_n}$。

然后只要求 $fib_n$ 就好了。

$n$ 极其大，递推会挂掉，考虑矩阵快速幂。

令初始矩阵为 $\begin{bmatrix}1 & 1 \\\end{bmatrix}$，转移矩阵为 $\begin{bmatrix}0 & 1 \\1 & 1\end{bmatrix}$。

则求初始矩阵乘上转移矩阵的 $n-1$ 次方。

这个方法不唯一，有其他的也可以。

但是发现题目里没给 $m$ 是质数，这个怎么办呢?

保证底数 $p$ 是质数，所以 $\gcd(p,m) = 1$，可以应用欧拉定理。

即：$p^{\varphi_m} \equiv 1 \pmod m$。

一个根号复杂度求出欧拉函数，然后在矩阵乘法时对其取模即可。

复杂度 $O(T\sqrt{m}+T\log n)$

记得特判 $m = 1$。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m,p;
int mod;
struct matrix{
	int x,y,z,w;
	matrix operator*(const matrix &k)const{
		return {(x*k.x+z*k.y)%mod,(y*k.x+w*k.y)%mod,(x*k.z+z*k.w)%mod,(y*k.z+w*k.w)%mod};
	}
};
int qpow(int b){
	matrix mat={0,1,1,1},res={1,0,1,0};
	b-=2;
	while(b>0){
		if(b&1) res=res*mat;
		mat=mat*mat,b>>=1;
	}
	// cout<<res.x<<' '<<res.z<<'\n';
	return res.z;
}
int pqow(int a,int b){
	a%=mod;
	int r=1;
	while(b){
		if(b&1) r=r*a%mod;
		a=a*a%mod,b>>=1;
	}
	return r;
}
int phi(int x){
	int ph=x;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			ph=ph/i*(i-1);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) ph=ph/x*(x-1);
	return ph;
}
signed main(){
	// ios::sync_with_stdio(0);
	// cin.tie(0),cout.tie(0);
	cin>>T>>p;
	mod=114514;
	while(T--){
		cin>>n>>m;
		if(m==1){
			cout<<0<<'\n';
			continue;
		}
		mod=phi(m);
		int b=qpow(n);
		mod=m;
		cout<<pqow(p,b)<<'\n';
	}
	return 0;
}

快速幂指数记得也要开longlong，否则挂50