跟YY的gcd如出一辙，得到一个显然的柿子
\[\prod_{k} F_{k}^{z}
\]
\[z= \sum _{d} \mu(d) \lfloor\frac{n}{kd} \rfloor \lfloor\frac{m}{kd} \rfloor
\]
那么我们设T=kd，
\[\prod _{T} \prod _{k|T} F_{k}^x
\]
\[x=\mu(\frac{T}{k}) \lfloor\frac{n}{T} \rfloor \lfloor\frac{m}{T} \rfloor
\]
注意到对于一块来说$$\lfloor\frac{n}{T} \rfloor \lfloor\frac{m}{T} \rfloor$$都是相同的。
我们只需处理
\[\prod _{k|T} F_{k}^y
\]
的前缀积，以及逆元的前缀积即可
\[y=\mu( \frac{T}{k})
\]
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef long long ll;
const ll mo=1e9+7;
const int N=1e6+5;
int p[N],tot,mu[N];
int j,k;
ll ans,f[N],x,inv[N],z,t[N],n,m,r;
bool vis[N];
ll power(ll a,ll b){
ll t=1,y=a%mo;
while (b) {
if (b&1) t=t*y%mo;
y=y*y%mo;
b/=2;
}
return t;
}
int main(){
// freopen("data.in","r",stdin);
f[0]=0; f[1]=1;
inv[1]=1;
fo(i,2,N-1) {
f[i]=(f[i-1]+f[i-2])%mo;
inv[i]=power(f[i],mo-2);
}
mu[1]=1;
fo(i,2,N-1){
if (!vis[i]) {
mu[i]=-1;
p[++tot]=i;
}
fo(j,1,tot) {
if ((ll)i*(ll)p[j] >= N) break;
vis[i*p[j]]=1;
if (i%p[j]==0) {
break;
}
else {
mu[i*p[j]]=-mu[i];
}
}
}
fo(i,0,N-1) t[i]=1;
fo(i,1,N-1) {
fo(j,1,(N-1)/i) {
if (mu[j]==0) z=1;
if (mu[j]==1) z=f[i];
if (mu[j]==-1) z=inv[i];
t[i*j]=t[i*j]*z%mo;
}
}
fo(i,1,N-1) t[i]=t[i]*t[i-1]%mo;
inv[0]=1;
fo(i,1,N-1) {
inv[i]=power(t[i],mo-2);
}
int Q;
scanf("%d",&Q);
while (Q--){
ans=1;
scanf("%lld %lld",&n,&m);
j=1;
while (j<=min(n,m)) {
r=min(n/(n/j), m/(m/j));
z=t[r]*inv[j-1]%mo;
z=power(z,(n/j)*(m/j));
ans=ans*z%mo;
j=r+1;
}
printf("%lld\n",ans);
}
return 0;
}