题意：求$\prod\limits_{i=1}^n\prod\limits_{j=1}^mf_{(i,j)}$，其中$f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}$
很妙的题
假设$n\leq m$，如果我们能找到一个$g$使得$f(n)=\prod\limits_{d|n}g(d)$，那么答案就是$\prod\limits_{d=1}^ng(d)^{\left\lfloor\frac nd\right\rfloor\left\lfloor\frac md\right\rfloor}$
然后直接把莫比乌斯反演搬过来居然也是可以的...我们得到$g(n)=\prod\limits_{d|n}f(d)^{\mu\left(\frac nd\right)}$
于是枚举$d$更新$d$的倍数就预处理出$g$了，时间复杂度$O\left(n\log_2n+T\sqrt n\log_2n\right)$
#include<stdio.h>
typedef long long ll;
const int mod=1000000007,T=1000000;
void swap(int&a,int&b){a^=b^=a^=b;}
int min(int a,int b){return a<b?a:b;}
int mul(int a,int b){return a*(ll)b%mod;}
int pow(int a,ll b){
int s=1;
while(b){
if(b&1)s=mul(s,a);
a=mul(a,a);
b>>=1;
}
return s;
}
int pr[T+10],mu[T+10],f[T+10],rf[T+10],g[T+10],rg[T+10];
bool np[T+10];
void sieve(){
int i,j,M=0;
mu[1]=1;
for(i=2;i<=T;i++){
if(!np[i]){
pr[++M]=i;
mu[i]=-1;
}
for(j=1;j<=M&&i*pr[j]<=T;j++){
np[i*pr[j]]=1;
if(i%pr[j]==0)break;
mu[i*pr[j]]=-mu[i];
}
}
}
int main(){
int cas,n,m,i,j,nex,s;
sieve();
f[0]=0;
f[1]=1;
for(i=2;i<=T;i++)f[i]=(f[i-1]+f[i-2])%mod;
for(i=1;i<=T;i++)rf[i]=pow(f[i],mod-2);
for(i=1;i<=T;i++)g[i]=1;
for(i=1;i<=T;i++){
if(mu[i]){
for(j=i;j<=T;j+=i)g[j]=mul(g[j],(mu[i]==1?f:rf)[j/i]);
}
}
for(i=2;i<=T;i++)g[i]=mul(g[i],g[i-1]);
for(i=1;i<=T;i++)rg[i]=pow(g[i],mod-2);
rg[0]=1;
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&m);
if(n>m)swap(n,m);
s=1;
for(i=1;i<=n;i=nex+1){
nex=min(n/(n/i),m/(m/i));
s=mul(s,pow(mul(g[nex],rg[i-1]),(ll)(n/i)*(m/i)));
}
printf("%d\n",(s+mod)%mod);
}
}