rt

就是根据第二篇题解我们有 $f_i=\prod_{d|i}g_i$，然后我们现在已知 $f$ 要求 $g$。

容易发现是一个 Dirichlet 前缀积的形式，我就想着做一下差分，然后就寄了。

不知道是因为正确性问题还是细节问题，求调和 hack。

#include <iostream>
#include <cstdio>

#define LL long long
#define MOD 1000000007
#define N 1000005

using namespace std;
int T,n,m; LL f[N],g[N];

int pcnt,p[N],vis[N];

void euler() {
    for (int i=2;i<N;i++) {
        if (!vis[i]) p[++pcnt]=i;
        for (int j=1;j<=pcnt and i*p[j]<N;j++) {
            vis[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

LL quickpow(LL a,int k) {
    LL res=1;
    while (k) {
        if (k&1) res=res*a%MOD;
        a=a*a%MOD,k>>=1;
    }
    return res;
}

int main() {
    scanf("%d",&T); euler();
    f[0]=0,f[1]=1;
    for (int i=2;i<N;i++) f[i]=(f[i-1]+f[i-2])%MOD;
    for (int i=1;i<=pcnt;i++)
        for (int j=1;p[i]*j<N;j++) f[p[i]*j]=f[p[i]*j]*quickpow(f[j],MOD-2)%MOD;
    for (int i=2;i<N;i++) f[i]=f[i]*f[i-1]%MOD; f[0]=1;
    while (T--) {
        scanf("%d%d",&n,&m);
        if (n>m) swap(n,m);
        LL ans=1;
        // for (int i=1;i<=n;i++) printf("%d: %lld\n",i,f[i]);
        for (int l=1,r=0;l<=n;l=r+1) {
            r=min(n/(n/l),m/(m/l));
            ans=ans*quickpow(f[r]*quickpow(f[l-1],MOD-2)%MOD,1ll*(n/l)*(m/l)%(MOD-1))%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}