$$ans=∏_{i=1}^{n}∏_{j=1}^{m}f_{gcd(i,j)}$$ $$=∏_{d=1}^{n}∏_{i=1}^{n}∏_{j=1}^{m} f_{gcd(i,j)}[gcd(i,j)=d]$$$$=∏_{d=1}^{n}(f_{d})^{Σ_{i=1}^{n/d}Σ_{j=1}^{m/d}[gcd(i,j)=1]}$$$$=∏_{d=1}^{n}(f_{d})^{Σ_{i=1}^{n/d}Σ_{j=1}^{m/d}[gcd(i,j)=1]}$$$$=∏_{d=1}^{n}(f_{d})^{Σ_{i=1}^{n/d}μ(i)(\frac{n}{id})(\frac{m}{id})}$$$$令T=id$$ $$ans=∏_{T=1}^{n}∏_{d|T}^{}(f_{d})^{(n/T)(m/T)*μ(\frac{T}{d})}$$$$=∏_{T=1}^{n}(∏_{d|T}^{}(f_{d})^{μ(\frac{T}{d})})^{(n/T)(m/T)}$$$$=∏_{T=1}^{n}(sum_{T})^{(n/T)(m/T)}$$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000000
#define mod 1000000007
int pr,p[N+10],mu[N+10];
bool v[N+10];
int f[N+10];
int sum[N];
int qpow(int a,int b){
	int res=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
	return res;
}
void init(){
	memset(v,0,sizeof(v));
	pr=0;mu[0]=0;mu[1]=1;
	f[0]=0,f[1]=1;sum[0]=sum[1]=1;
	for(int i=2;i<=N;i++){
		f[i]=(f[i-1]+f[i-2])%mod;
		sum[i]=1;
		if(!v[i])p[++pr]=i,mu[i]=-1,v[i]=1;
		for(int j=1;j<=pr&&i*p[j]<=N;j++){
			v[i*p[j]]=1;
			if(i%p[j]==0){
				mu[i*p[j]]=0;
				break;
			}
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++)if(mu[i]){
		for(int j=1;i*j<=N;j++){
			sum[i*j]=sum[i*j]*(mu[i]==1?f[j]:qpow(f[j],mod-2))%mod;
		}
	}
	for(int i=2;i<=N;i++)sum[i]=sum[i]*sum[i-1]%mod;
}
int calc(int n,int m){
	if(n>m)swap(n,m);
	int ans=1;
	for(int l=1,r;l<=n;l=r+1){
		r=min(n/(n/l),m/(m/l));
		ans=ans*qpow(sum[r]*qpow(sum[l-1],mod-2)%mod,(n/l)*(m/l)%(mod-1))%mod;
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	init();
	int t;cin>>t;
	while(t--){
		int n,m;cin>>n>>m;
		cout<<calc(n,m)<<'\n';
	}
	
	return 0;
}

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6;
const LL mod=1e9+7;
int pr, p[N+10];LL mu[N+10],F[N+10]; bool v[N+10];
void init()
{
	memset(v,0,sizeof(v));
	pr=0;mu[0]=0;mu[1]=1;
    for(int i=2;i<=N;i++)
	{
        if(!v[i]) p[++pr]=i, mu[i]=-1; 
        for(int j=1;j<=pr&&p[j]*i<=N;j++)
		{
            v[i*p[j]]=true;
            if(i%p[j]==0){mu[i*p[j]]=0;break;}
            mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<=N;i++) mu[i]+=mu[i-1];
    F[0]=0;F[1]=1;for(int i=2;i<=N;i++)F[i]=(F[i-1]+F[i-2])%mod;
    F[0]=1;for(int i=2;i<=N;i++)F[i]=F[i]*F[i-1]%mod;
}
LL calc(LL n,LL m)
{
	LL res=0;
    for(LL l=1,r;l<=n;l=r+1)
	{
        r=min(n/(n/l), m/(m/l));
        res+=(mu[r]-mu[l-1])*(n/l)*(m/l);
    }
    return res;
}
LL qpow(LL a,LL b){LL res=1;for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;return res;}
int main()
{
	init();
	int T;scanf("%d",&T);
	while(T--)
	{
        LL n,m;scanf("%lld%lld",&n,&m);if(n>m)swap(n,m); 
        LL ans=1;
		for(LL l=1,r;l<=n;l=r+1)
		{
			r=min(n/(n/l),m/(m/l));
			LL tn=n/l, tm=m/l;
			LL g=calc(tn,tm);
			ans=ans*qpow(F[r]*qpow(F[l-1],mod-2)%mod,g)%mod;	
    	}
        printf("%lld\n",ans);
	}
    return 0;
}