#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1000006, Md = 1e9 + 7, Ph = 1e9 + 6;
const int P = 100005;
int p[P], pc, mo[N];
int f[N], inv[N], prod[N], iprod;
bitset<N> notp;
inline void mobius(int Mx)
{
    notp[1] = 1;
    mo[1] = 1;
    for(int i = 2; i <= Mx; ++i)
    {
        if(!notp[i])
        {
            mo[i] = -1;
            p[++pc] = i;
        }
        for(int j = 1; j <= pc && i * p[j] <= Mx; ++j)
        {
            notp[i * p[j]] = 1;
            if(i % p[j] == 0) break;
            else mo[i * p[j]] = -mo[i];
        }
    }
    for(int i = 1; i <= Mx; ++i)
    {
        mo[i] += mo[i - 1];
    }
}
inline ll qp(ll b, ll e, ll mod)
{
    b %= mod;
    ll res = 1;
    while(e)
    {
        if(e & 1)
        {
            res = (res * b) % mod;
        }
        b = (b * b) % mod;
        e >>= 1;
    }
    return res;
}
inline void Fib(int Mx)
{
    f[1] = 1;
    f[2] = 1;
    for(int i = 3; i <= Mx; ++i)
    {
        f[i] = (f[i - 1] + f[i - 2]) % Md;
    }
    for(int i = 2; i <= Mx; ++i)
    {
        f[i] = ll(f[i]) * f[i - 1] % Md;
    }
    prod[0] = 1;
    prod[1] = f[1];
    for(int i = 2; i <= Mx; ++i)
    {
        prod[i] = ll(prod[i - 1]) * f[i] % Md; 
    }
    iprod = qp(prod[Mx], Md - 2, Md);
    for(int i = Mx; i; --i)
    {
        inv[i] = ll(iprod) * prod[i - 1] % Md;
        iprod = ll(iprod) * f[i] % Md;
    }
    inv[0] = 1;
    return;
}

inline ll S(int p, int q)
{
    ll ans = 0;
    for(int l = 1, r; l <= p; l = r + 1)
    {
        r = min(p / (p / l), q / (q / l));
        ans += ll(mo[r] - mo[l - 1]) * (ll(p / l) * (q / l) % Ph) % Ph;
        ans %= Ph;
    }
    return ans;
}
inline ll A(int n, int m)
{
    ll res = 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));
        ll prodF = ll(f[r]) * inv[l - 1] % Md;
        ll Sres = S(n / l, m / l);
        // printf("pF%lld Sr%lld\n", prodF, Sres);
        res = qp(prodF, Sres, Md) * res % Md;
    }
    return res;
}
int T;
template<class io>
inline void re(io &x)
{
    char c=getchar();x=0;
    while(c<48 || c>57)c=getchar();
    while(c>47 && c<58)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return;
}
template<class io>
void wr(io x)
{
    io d=x/10; if(d) wr(d);
    putchar(x-(d<<3)-(d<<1)|48); return;
}
signed main()
{
    freopen("numtab.in", "r", stdin);
    mobius(N - 5);
    Fib(N - 5);
    // for(int i = 1; i <= 5; ++i)
    // {
    //     printf("%d\n", inv[i]);
    // }puts("");
    // for(int i = 1; i <= 5; ++i)
    // {
    //     printf("%d\n", f[i]);
    // }
    re(T);
    while(T--)
    {
        int n, m;
        re(n); re(m);
        wr(A(n, m));putchar('\n');
    }
    return 0;
}

复杂度是不对的（我只是打个暴力）但问题不在这里；

输入1 100000 20000很快就算完了

输入1 100000 30000就TLE了