$$\prod _ {i = 1} ^ n \prod _ {j = 1} ^ m f _ {gcd(i, j)}$$

（其实可以把问题出成 $gcd(f _ i, f _ j)$，这样还得多一个套路嘿嘿嘿）

\begin{aligned} &\prod _ {i = 1} ^ n \prod _ {j = 1} ^ m f _ {gcd(i, j)}\\ =&\prod _ {d = 1} ^ n \prod _ {i = 1} ^ n \prod _ {j = 1} ^ m [gcd(i, j) = d] \times f _ d\\ =&\prod _ {d = 1} ^ n f _ d ^ {\sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor} [gcd(i, j) == 1]} \end{aligned}

\begin{aligned} &\sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor} [gcd(i, j) == 1]\\ =&\sum _ {t = 1} ^ {\lfloor \frac n d \rfloor} \mu(t) \lfloor \frac n {dt} \rfloor \lfloor \frac m {dt} \rfloor \end{aligned}

\begin{aligned} &\prod _ {T = 1} ^ n \prod _ {d | T} f _ d ^ {\mu(\frac T d) \lfloor \frac n T \rfloor \lfloor \frac m T \rfloor}\\ =&\prod _ {T = 1} ^ n (\prod _ {d | T} f _ d ^ {\mu(\frac T d)}) ^ {\lfloor \frac n T \rfloor \lfloor \frac m T \rfloor} \end{aligned}

#include <bits/stdc++.h>

#define NS (1000001)
#define MOD (1000000007)
#define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD)
#define mns(a, b) ((a) - (b) < 0 ? (a) - (b) + MOD : (a) - (b))
#define mul(a, b) (1ll * (a) * (b) % MOD)
#define Inv(a) (qpow((a), MOD - 2))

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = mul(res, a);
a = mul(a, a), b >>= 1;
}
return res;
}

int testcase, n, m, p[NS], cnt, mu[NS], f[NS], g[NS], ng[NS], ans;

bool vis[NS];

void preWork()
{
mu[1] = f[1] = 1;
for (int i = 2; i < NS; i += 1)
{
f[i] = pls(f[i - 1], f[i - 2]);
if (!vis[i]) p[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt; j += 1)
{
int k = i * p[j];
if (k >= NS) break;
vis[k] = 1, mu[k] = -mu[i];
if (i % p[j] == 0) { mu[k] = 0; break; }
}
}
fill(g, g + NS, 1), fill(ng, ng + NS, 1);
for (int i = 1; i < NS; i += 1)
{
int iv = Inv(f[i]);
for (int j = i; j < NS; j += i)
{
if (!mu[j / i]) continue;
if (mu[j / i] > 0) g[j] = mul(g[j], f[i]), ng[j] = mul(ng[j], iv);
else g[j] = mul(g[j], iv), ng[j] = mul(ng[j], f[i]);
}
}
for (int i = 1; i < NS; i += 1)
g[i] = mul(g[i], g[i - 1]), ng[i] = mul(ng[i], ng[i - 1]);
}

int main(int argc, char const* argv[])
{
IN(testcase), preWork();
while (testcase--)
{
IN(n), IN(m), ans = 1;
if (n > m) swap(n, m);
for (int l = 1, r; l <= n; l = r + 1)
{
r = min(n / (n / l), m / (m / l));
int x = mul(g[r], ng[l - 1]);
ans = mul(ans, qpow(qpow(x, n / l), m / l));
}
printf("%d\n", ans);
}
return 0;
}


#### Remmina

No puzzle that couldn't be solved.