$$\prod_{d=1}^{n}\prod_{i=1}^{n}\prod_{j=1}^{m}if(gcd(i,j)=d) f[d]$$
$$=\prod_{d=1}^{n}\prod_{i=1}^{n}\prod_{j=1}^{m}if(gcd(i,j)=d) f[d]$$
$$=\prod_{d=1}^{n}\prod_{i=1}^{ \lfloor\frac{n}{d}\rfloor }\prod_{j=1}^{ \lfloor\frac{m}{d}\rfloor }if(gcd(i,j)=1) f[d]$$
$$=\prod_{d=1}^{n} f[d]^{\sum_{i=1}^{ \lfloor\frac{n}{d}\rfloor }\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]}$$

$\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor }\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]​$ 是个熟悉的式子，我们从这个式子继续开刀：

$$\sum_{i=1}^{ \lfloor\frac{n}{d}\rfloor }\sum_{j=1}^{ \lfloor\frac{m}{d}\rfloor }[gcd(i,j)=1]​$$
$$=\sum_{i=1}^{ \lfloor\frac{n}{d}\rfloor }\sum_{j=1}^{ \lfloor\frac{m}{d}\rfloor }\sum_{x|gcd(i,j)} \mu(x)​$$
$$=\sum_{x=1}^{n}\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor​$$

$$\prod_{d=1}^{n} f[d]^{\sum_{x=1}^{n}\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor}​$$

$$\prod_{d=1}^{n} f[d]^{\sum_{x=1}^{n}\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor}​$$

$$=\prod_{T=1}^{n}\prod_{d|T} f[d]^{\mu( \lfloor\frac{T}{d}\rfloor )\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}$$
$$=\prod_{T=1}^{n}(\prod_{d|T} f[d]^{\mu( \lfloor\frac{T}{d}\rfloor )})^{\lfloor\frac{n}{T}{\rfloor\lfloor\frac{m}{T}\rfloor}}$$

### Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e6+2;
#define MOD 1000000007

template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}

bool vis[N+15];
int mui[N+15],inv[N+15],fib[N+15],sum[N+15],prime[N],cnt;
inline int pow(int x,int y) {
int res=1;
for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) res=1ll*res*x%MOD;
return res%MOD;
}

inline void pre() {
fib[1]=inv[1]=sum[0]=sum[1]=1;
vis[1]=true,mui[1]=1;
for(int i=2;i<=N;++i) {
fib[i]=(fib[i-1]+fib[i-2])%MOD;
inv[i]=pow(fib[i],MOD-2),sum[i]=1;
if(!vis[i]) prime[++cnt]=i,mui[i]=-1;
for(int j=1;j<=cnt&&i*prime[j]<=N;++j) {
vis[i*prime[j]]=1;
if(!(i%prime[j])) break;
else mui[i*prime[j]]=-mui[i];
}
}
for(int d=1;d<=N;++d) {
if(!mui[d]) continue;
for(int T=d;T<=N;T+=d)
sum[T]=1ll*sum[T]*(mui[d]==1?fib[T/d]:inv[T/d])%MOD;
}
for(int i=2;i<=N;++i) sum[i]=1ll*sum[i]*sum[i-1]%MOD;
return;
}

int T,n,m;
int main() {
pre(),IN(T);
while(T--) {
IN(n),IN(m);
if(n>m) swap(n,m);
int ans=1,res,num;
for(int l=1,r=0;l<=n;l=r+1) {
r=min(n/(n/l),m/(m/l));
num=1ll*(n/l)*(m/l)%(MOD-1);
res=1ll*sum[r]*pow(sum[l-1],MOD-2)%MOD;
ans=1ll*ans*pow(res,num)%MOD;
}
printf("%d\n",(ans+MOD)%MOD);
}
return 0;
}

QAQ