这个题的难点在于，与一般的反演的sigma和乘法不同，这个反演题是pi和乘方。

但是，乘法乘方也有优秀的运算律，所以可以做。

 

fib没有什么可以好的可以卷积的性质，那就单独考虑。

枚举fib的第k项，统计贡献，

指数的位置直接莫比乌斯反演。

剩下k*d这样的

套路地，考虑枚举D=k*d

（争取化成枚举约数的形式，比较好处理）

（而且可以把指数位置的sigma拿出来，分离（这个很关键））

外面枚举的k从1到n，里面的d从1到n/k

所以，D的范围恰好是1到n

然后就可以枚举D，枚举k为D的约数。里面就是d=D/k了。（本质利用a^(x+y)=a^x*a^y）来处理的。

然后

中间括号的函数可以枚举约数然后nlogn处理

之后根号分块即可。

注意1,2一些开始的递推初值赋值，以及它们的逆元别漏掉。

#include
     
      #define il inline#define reg register int#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=1e6+5;const int mod=1e9+7;ll fib[N],inv[N];//inv of fibint n,m,t;int miu[N],vis[N],pri[N],tot;ll g[N],ig[N];//inv of g[]ll qm(ll x,ll y){    ll ret=1;    while(y){        if(y&1) ret=((ll)ret*x)%mod;        x=((ll)x*x)%mod;        y>>=1;    }    return ret;}void sieve(){    miu[1]=1;    for(reg i=2;i<=N-3;++i){        if(!vis[i]){            vis[i]=1;            miu[i]=-1;            pri[++tot]=i;        }        for(reg j=1;j<=tot;++j){            if((ll)pri[j]*i>N-3) break;            vis[pri[j]*i]=1;            if(i%pri[j]==0){                miu[i*pri[j]]=0;                break;            }            else{                miu[i*pri[j]]=miu[i]*miu[pri[j]];            }        }    }}int main(){    rd(t);    sieve();    fib[0]=0,fib[1]=1,fib[2]=1;    inv[1]=1,inv[2]=1;    g[1]=1,g[2]=1;    for(reg i=3;i<=N-3;++i) {        fib[i]=(fib[i-1]+fib[i-2])%mod;        g[i]=1;            inv[i]=qm(fib[i],mod-2);        //cout<
      
       <<" "<
       
        <
        
         m) swap(n,m);        ll ans=1;        for(reg i=1,x=0;i<=n;i=x+1){            x=min(n/(n/i),m/(m/i));            ans=(ans*qm((g[x]*ig[i-1])%mod,((ll)(n/i)*(m/i))%(mod-1)))%mod;        }        printf("%lld\n",ans);    }    return 0;}}signed main(){    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2018/12/13 11:20:35*/