求调/kel

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll mod = 1e9+7;
const int N = 1e6+6;

ll pw(ll x,ll y){
	ll res=1;
	if (y<0){
		y+=mod-1;
	}
	while (y){
		if (y&1){
			res=res*x%mod;
		}
		x=x*x%mod;
		y>>=1;
	}
	return res;
}

ll pr[N],cnt,mu[N],vis[N],fb[N],f[N];
void init(){
	mu[1]=1;
	for (int i=2; i<N; i++){
		if (!vis[i]){
			mu[i]=-1;
			pr[++cnt]=i;
		}
		for (int j=1; j<=cnt && i*pr[j]<N; j++){
			vis[i*pr[j]]=1;
			if (i%pr[j]==0){
				break;
			}
			else{
				mu[i*pr[j]]=-mu[i];
			}
		}
	}
	fb[0]=0;
	fb[1]=1;
	for (int i=2; i<N; i++){
		fb[i]=(fb[i-1]+fb[i-2])%mod;
	}
	for (int i=1; i<N; i++){
		f[i]=1;
	}
	for (int i=1; i<N; i++){
		for (int j=i; j<N; j+=i){
			f[j]=f[j]*pw(fb[i],mu[j/i])%mod;
		}
	}
	for (int i=2; i<N; i++){
		f[i]=f[i-1]*f[i]%mod;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin>>t;
	init();
	while (t--){
		ll n,m;
		cin>>n>>m;
		if (n>m){
			swap(n,m);
		}
		ll ans=1,j;
		for (ll i=1; i<=n; i=j+1){
			j=min(n/(n/i),m/(m/i));
			ans=ans*pw(f[j]*(i==1?1ll:pw(f[i-1],mod-2))%mod,(n/i)*(m/i)%mod)%mod;
		}
		cout<<ans<<"\n";
	}
	return 0;
}