1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<bits/stdc++.h>
#define REG register
using namespace std;
const int N=1e6+10,Mod=1e9+7,PMod=1e9+6;
typedef pair<int,int> pii;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
int Pow(int a,int b){
int ans=1;
while(b){
if(b&1) ans=1ll*ans*a%Mod;
a=1ll*a*a%Mod,b>>=1;
}
return ans;
}
int T,n,m;
int F[N],P[N],I[N];
int Prm[N],vis[N],cnt,Mu[N];
map<pii,int> M;
inline void Init(){
F[1]=1;
for(REG int i=2;i<=1e6;++i) F[i]=(F[i-1]+F[i-2])%Mod;
P[0]=I[0]=1;
for(REG int i=1;i<=1e6;++i) P[i]=1ll*P[i-1]*F[i]%Mod;
I[(int)1e6]=Pow(P[(int)1e6],Mod-2);
for(REG int i=1e6-1;i;--i) I[i]=1ll*I[i+1]*F[i+1]%Mod;
Mu[1]=1;
for(REG int i=2;i<=1e6;++i){
if(!vis[i]) Prm[++cnt]=i,Mu[i]=PMod-1;
for(REG int j=1;j<=cnt&&i*Prm[j]<=1e6;++j){
vis[i*Prm[j]]=1;
if(i%Prm[j]==0) break;
Mu[i*Prm[j]]=PMod-Mu[i];
}
}
for(REG int i=1;i<=1e6;++i) Mu[i]=(Mu[i-1]+Mu[i])%PMod;
}
inline int G_Init(int n,int m){
int l=1,r=0,G=0;
for(;l<=n;l=r+1)
r=min(n,min(n/(n/l),m/(m/l))),G=(G+1ll*(PMod+Mu[r]-Mu[l-1])*(n/l)%PMod*(m/l)%PMod)%PMod;
return G;
}
inline void Work(){
Init();
read(T);
while(T--){
read(n),read(m);
if(n>m) swap(n,m);
M.clear();
int Ans=1;
int l=1,r=0;
for(;l<=n;l=r+1)
r=min(n,min(n/(n/l),m/(m/l))),Ans=1ll*Ans*Pow(1ll*P[r]*I[l-1]%Mod,G_Init(n/l,m/l))%Mod;
printf("%d\n",Ans);
}
}
int main(){Work();}
|
