Description：

设 $f(x)$ 为斐波那契数，求： $$ \prod_{i=1}^n\prod_{j=1}^mf(\gcd(i,j)) $$ $1\leqslant testcases\leqslant 10^3,1\leqslant n\leqslant 10^6$

Solution：

假设 $n\geqslant m$ 。

首先推一下就会发现，化成 $\varphi$ 是没有什么前途的，只能化成 $\mu$ 然后反演，枚举一下 $\gcd$ 然后再反演就会得到： $$ \prod_{d=1}^nf(d)^{\begin{align}\sum_{d'=1}^{\lfloor\frac n d\rfloor}\mu(d')\lfloor\frac n{dd'}\rfloor\lfloor\frac m{dd'}\rfloor\end{align}} $$ 这个时候根据套路要设 $T=dd'$ ，然后就会有： $$ \prod_{T=1}^n\prod_{d|T}f(d)^{\mu(\frac T d)\lfloor\frac n T\rfloor\lfloor\frac m T\rfloor} $$ 看数据范围怎么也得是一个 $O(t\sqrt n)$ 或者差不多的，这时有一个非常巧妙的我没想到的转化：后面 $\lfloor\frac n T\rfloor\lfloor\frac m T\rfloor$ 都和 $d$ 没关系，于是设： $$ val(T)=\prod_{d|T}f(d)^{\mu(\frac T d)} $$ 这个是可以 $O(n\ln n)$ 预处理的。

然后： $$ \prod_{T=1}^nval(T)^{\lfloor\frac n T\rfloor\lfloor\frac m T\rfloor} $$ 除法分块就可以了。

反演题：牢记套路，适时收手，观察式子的性质，多方面考虑。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1000010

#define MOD 1000000007

int fib[MAXN],val[MAXN],sumv[MAXN];

int power(int a,int b)

{

	b = (b + MOD - 1) % (MOD - 1);

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int prime[MAXN],tot = 0;

bool isprime[MAXN];

int mu[MAXN];

void init()

{

	for(int i = 2;i < MAXN;++i)isprime[i] = true;

	mu[1] = 1;

	for(int i = 2;i < MAXN;++i)

	{

		if(isprime[i])mu[i] = -1,prime[++tot] = i;

		for(int j = 1;j <= tot && i * prime[j] < MAXN;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0){mu[i * prime[j]] = 0;break;}

			else mu[i * prime[j]] = -1 * mu[i];

		}

	}

	fib[0] = 0;fib[1] = 1;

	for(int i = 2;i < MAXN;++i)fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;

	for(int t = 1;t < MAXN;++t)val[t] = 1;

	for(int d = 1;d < MAXN;++d)

		for(int t = d;t < MAXN;t += d)

			val[t] = 1ll * val[t] * power(fib[d],mu[t / d]) % MOD;

	sumv[0] = 1;

	for(int i = 1;i < MAXN;++i)sumv[i] = 1ll * sumv[i - 1] * val[i] % MOD;

	return;

}

void work()

{

	scanf("%d%d",&n,&m);

	if(n < m)swap(n,m);

	int ans = 1;

	for(int l = 1,r;l <= m;l = r + 1)

	{

		r = min(n / (n / l),m / (m / l));

		ans = 1ll * ans * power(1ll * sumv[r] * power(sumv[l - 1] % MOD,MOD - 2) % MOD,1ll * (n / l) * (m / l) % (MOD - 1)) % MOD;

	}

	cout << ans << endl;

	return;

}

int main()

{

	init();

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}