## 题目喵述

($n,m \leq 10^6$，数据组数 $T \leq 10^3$) 求

$$\prod_{i=1}^n\prod_{j=1}^m fib[gcd(i,j)]$$

## 喵解

$$g(d)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]$$

$$ans=\prod_{d=1}^nfib[d]^{g(d)}$$

$$g(d)=\sum_{i=1}^{\frac n d}\sum_{j=1}^{\frac m d}[gcd(i,j) == 1]$$

$$g(d)=\sum_{i=1}^{\frac n d} \mu(i)[\frac n {id}][\frac m {id}]$$

\begin{align} ans&=\prod_{d=1}^nfib[d]^{\sum_{i=1}^{\frac n d} \mu(i)[\frac n {id}][\frac m {id}]}\\ &=\prod_{d=1}^n\prod_{i=1}^{\frac n d} fib[d]^{\mu(i)[\frac n {id}][\frac m {id}]} \end{align}

$$\prod_{T=1}^n\prod_{d|T} fib[d]^{\mu(\frac n d)[\frac n T][\frac m T]}$$

$$\prod_{T=1}^n(\prod_{d|T} fib[d]^{\mu(\frac n d)})^{[\frac n T][\frac m T]}$$

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)

#define mod 1000000007
#define N 1000005
#define ll long long
std::bitset<N> vis;
ll mu[N], p[N], tot, up, fib[N], pd[N];
inline ll pow (ll x, ll y = mod - 2)
{
ll ret = 1;
while (y)
{
if (y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
inline void init ()
{
up = N - 3;
fib[0] = 0; fib[1] = 1; pd[0] = 1; pd[1] = 1;
fo (i, 2, up) {fib[i] = (fib[i - 1] + fib[i - 2]) % mod; pd[i] = 1;}
mu[1] = 1;
fo (i, 2, up)
{
if (!vis[i])
p[++tot] = i, mu[i] = -1;
vis[i] = 1;
for (int j = 1; j <= tot && i * p[j] <= up; ++j)
{
vis[i * p[j]] = 1;
if (!(i % p[j])) {break;}
mu[i * p[j]] = -mu[i];
}
}
fo (d, 1, up)
for (int T = d, div = 1; T <= up; T += d, ++div) // div = T / d
if (mu[div])
pd[T] = pd[T] * ((mu[div] == 1) ? fib[d] : pow(fib[d])) % mod;
fo (i, 2, up)
pd[i] = pd[i] * pd[i - 1] % mod;
}
int main()
{
int T;
scanf("%d", &T);
init();
while (T--)
{
ll n, m, ans = 1;
scanf("%lld %lld", &n, &m);
if (n > m) std::swap(n, m);
for (int i = 1, j; i <= n; i = j + 1)
{
j = std::min(n / (n / i), m / (m / i));
ans = ans * pow(pd[j] * pow(pd[i - 1]) % mod, (n / i) * (m / i) % (mod - 1)) % mod;
}
printf("%lld\n", ans);
}
return 0;
}