题意：
求[prodlimits_{i=1}^nprodlimits_{j=1}^mfib_{gcd(i,j)} ](T) 组测试数据，(1 leq T leq 10^3)，(1 leq n,m leq 10^6)
没啥好说的，直接推式子。
[egin{aligned}ans&=prodlimits_{i=1}^nprodlimits_{j=1}^mfib_{gcd(i,j)}\&=prodlimits_{d=1}^{min(n,m)}prodlimits_{i=1}^nprodlimits_{j=1}^mfib_d imes[gcd(i,j)=d]\&=prodlimits_{d=1}^{min(n,m)}fib_d^{sumlimits_{i=1}^{lfloorfrac{n}{d}
floor}sumlimits_{j=1}^{lfloorfrac{m}{d}
floor}[gcd(i,j)=1]}end{aligned}
]
设指数上的那一大堆玩意儿为 (M)，那么
[egin{aligned}M&=sumlimits_{i=1}^{lfloorfrac{n}{d}
floor}sumlimits_{j=1}^{lfloorfrac{m}{d}
floor}[gcd(i,j)=1]\&=sumlimits_{i=1}^{lfloorfrac{n}{d}
floor}sumlimits_{j=1}^{lfloorfrac{m}{d}
floor}sumlimits_{p|gcd(i,j)}mu(p)\&=sumlimits_{p=1}^{lfloorfrac{min(n,m)}{d}
floor}mu(p) imeslfloorfrac{n}{dp}
floorlfloorfrac{m}{dp}
floorend{aligned}
]
[egin{aligned}ans&=prodlimits_{d=1}^{min(n,m)}fib_d^M\&=prodlimits_{d=1}^{min(n,m)}fib_d^{sumlimits_{p=1}^{lfloorfrac{min(n,m)}{d}
floor}mu(p) imeslfloorfrac{n}{dp}
floorlfloorfrac{m}{dp}
floor}\&=prodlimits_{t=1}^{min(n,m)}prodlimits_{d|t}fib_d^{mu(frac{t}{d}) imeslfloorfrac{n}{t}
floorlfloorfrac{m}{t}
floor}\&=prodlimits_{t=1}^{min(n,m)}(prodlimits_{d|t}fib_d^{mu(frac{t}{d})})^{lfloorfrac{n}{t}
floorlfloorfrac{m}{t}
floor}end{aligned}
]
把括号里的东西预处理出来然后整除分块就行了
/*
Contest: -
Problem: P3704
Author: tzc_wk
Time: 2020.9.16
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a) a.begin(),a.end()
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,0x3f,sizeof(a))
#define y1 y1010101010101
#define y0 y0101010101010
#define int long long
typedef pair<int,int> pii;
typedef long long ll;
inline int read(){
int x=0,neg=1;char c=getchar();
while(!isdigit(c)){
if(c=='-') neg=-1;
c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*neg;
}
const int MOD=1e9+7;
inline int qpow(int x,int e){
if(!x) return 1;
int ans=1;
while(e){
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
int f[1000005],mu[1000005],p[1000005],pcnt=0,F[1000005];
bool vis[1000005];
inline void prework(int n){
f[1]=f[2]=1;
for(int i=3;i<=n;i++)
f[i]=(f[i-1]+f[i-2])%MOD;
mu[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){p[++pcnt]=i;mu[i]=-1;}
for(int j=1;j<=pcnt&&p[j]*i<=n;j++){
vis[i*p[j]]=1;
if(i%p[j]==0) break;
mu[i*p[j]]=-mu[i];
}
}
for(int i=1;i<=n;i++) F[i]=1;
for(int i=1;i<=n;i++){
int inv=qpow(f[i],MOD-2);
for(int j=i;j<=n;j+=i){
if(!mu[j/i]) continue;
else if(~mu[j/i]) F[j]=F[j]*f[i]%MOD;
else F[j]=F[j]*inv%MOD;
}
}
for(int i=2;i<=n;i++)
F[i]=F[i-1]*F[i]%MOD;
}
signed main(){
prework(1e6);
int T=read();
while(T--){
int n=read(),m=read(),ans=1;
for(int l=1,r;l<=min(n,m);l=r+1){
r=min(n/(n/l),m/(m/l));
ans=(ans*(qpow(F[r]*qpow(F[l-1],MOD-2)%MOD,(n/l)*(m/l)%(MOD-1))))%MOD;
}
printf("%lld
",ans);
}
return 0;
}