PUZZLE

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int MOD = 1e9 + 7;
const int LIM = 1e6;

int fixMOD(ll v){
    v %= MOD;
    if (v < 0) v += MOD;
    return v;
}

int subMOD(int x, int y){
    return fixMOD(x -= y);
}

int mulMOD(ll x, ll y){
    x %= MOD;
    y %= MOD;
    return fixMOD(x * y);
}

int fact[LIM + 10];
int tcaf[LIM + 10];
int invs[LIM + 10];

void precal(int n = LIM){
    fact[0] = fact[1] = 1;
    tcaf[0] = tcaf[1] = 1;
    invs[0] = invs[1] = 1;
    for (int i = 2; i <= n; ++i){
        fact[i] = mulMOD(fact[i - 1], i);
        invs[i] = fixMOD(MOD - mulMOD(MOD / i, invs[MOD % i]));
        tcaf[i] = mulMOD(tcaf[i - 1], invs[i]);
    }
}

int nck(int n, int k){
    if (k < 0 || k > n) return 0;
    return mulMOD(fact[n], mulMOD(tcaf[k], tcaf[n - k]));
}

int m,n;
long long x;
long long path;
int pcnt[LIM];
int pos;

void factorize(vector<int> &S,long long x, int n){
    for (int i = 1; i * i <= n; ++i) if (n % i == 0){
        if (x % i == 0) S.push_back(i);
        int j = n / i;
        if (i != j && x % j == 0) S.push_back(j);
    }
}

long long pathSum(vector<int> S,int pos){
    int k = S[pos];
    long long cnt = nck(m/k+n/k,n/k);
    if(k==1){
        pcnt[1] = 1;
        return cnt%MOD;
    }
    int mul = k;
    pos--;
    while(pos >=0){
        if(k % S[pos] == 0){
            mul -= pcnt[S[pos]];
        }
        pos--;
    }
    pcnt[k] = mul;
    return (long long)(mul*cnt)%MOD;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    precal();
    while(t--){
        path =0;
        cin >> x >> m >> n;
        if(m == 1 && n ==1){
            cout << mulMOD(x, x) << '\n';
            continue;
        }else if(n==1 || m == 1){
            cout << x%MOD << '\n';
            continue;
        }
        if(m > n) swap(m,n);
        m--,n--;
        vector<int> S;
        factorize(S, x, n);
        factorize(S, x, m);
        sort(S.begin(),S.end());
        S.resize(unique(S.begin(),S.end()) - S.begin());
        int sz = S.size();
        for(int i=0;i<sz;i++){
            path = (path+pathSum(S,i)) %MOD;
        }
        cout << path << '\n';
    }
}