きりま しゃろ 、お誕生日おめでとうございます！

传送门

设$g(k)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=k]$

$g$的反演就很老套了，$g(k)=\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\left\lfloor\dfrac{n}{kd}\right\rfloor\left\lfloor\dfrac{m}{kd}\right\rfloor$

直接枚举$gcd$：

$\prod\limits_{i=1}^n\prod\limits_{j=1}^mf(gcd(i,j))$

$=\prod\limits_{d=1}^nf(d)^{g(d)}$

$=\prod\limits_{d=1}^nf(d)^{\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor}$

推到这里复杂度是$O(T(n^{\frac{3}{4}}+\sqrt{n}\log n))$的，然而常数太大过不去。

设$T=id$，有$d|T$，枚举$T$：

$=\prod\limits_{d=1}^nf(d)^{\sum\limits_{T=1}^n[d|T]\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}$

$=\prod\limits_{T=1}^n\left(\prod\limits_{d|T}f(d)^{\mu(\frac{T}{d})}\right)^{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}$

预处理出$f$的前缀积、前缀逆元和$\prod\limits_{d|T}f(d)\mu(\frac{T}{d})$就能$O(T\sqrt{n}\log n)$做了。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 1000001
#define inf 0x3f3f3f3f

const int mod = 1e9 + 7;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int mu[maxn],prime[maxn>>2],f[maxn]={0,1},g[maxn]={1,1},pre[maxn]={1},inv[maxn]={1},cnt;
bool is[maxn];
int INV(int x){return x==1?1:1ll*(mod-mod/x)*INV(mod%x)%mod;}
int quickpow(int x,int y){
    int ans=1;
    while(y){
        if(y&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return ans;
}
void workinv(){
    int all=INV(pre[maxn-1]),now=1;
    for(register int i=maxn-1;i;--i)inv[i]=1ll*all*now%mod*pre[i-1]%mod,now=1ll*now*g[i]%mod;
}
int main(){
    is[1]=mu[1]=1;
    for(register int i=2;i<maxn;++i){
        f[i]=(f[i-1]+f[i-2])%mod,g[i]=1;
        if(!is[i])prime[++cnt]=i,mu[i]=-1;
        for(register int j=1;j<=cnt&&i*prime[j]<maxn;++j){
            is[i*prime[j]]=1;
            if(i%prime[j]==0){mu[i*prime[j]]=0;break;}
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(register int i=1;i<maxn;++i){
        int p=INV(f[i]);
        for(register int j=i;j<maxn;j+=i){
            if(mu[j/i]==-1)g[j]=1ll*g[j]*p%mod;
            else if(mu[j/i]==1)g[j]=1ll*g[j]*f[i]%mod;
        }
    }
    for(register int i=1;i<maxn;++i)mu[i]+=mu[i-1],g[i]=1ll*g[i-1]*g[i]%mod,pre[i]=1ll*pre[i-1]*g[i]%mod;
    workinv();
    int t=read(),n,m,ans;
    while(t--){
        n=read(),m=read(),ans=1;
        if(n>m)swap(n,m);
        for(register int l=1,r;l<=n;l=r+1){
            r=min(n/(n/l),m/(m/l));
            ans=1ll*ans*quickpow(1ll*g[r]*inv[l-1]%mod,1ll*(n/l)*(m/l)%(mod-1))%mod;
        }
        printf("%d\n",ans);
    }
}