Big Integer Code

///Big Integer (Only For Positive Numbers).
#include <bits/stdc++.h>
using namespace std;

typedef int64_t ll;
typedef long long ll;
typedef pair<ll,ll> lll;
typedef pair<ll,int> lli;
typedef pair<int,int> ii;
#define EL printf("\n")
#define OK printf("OK")
#define pb push_back
#define mp make_pair
#define ep emplace_back
#define X  first
#define Y  second
#define fillchar(a,x) memset(a, x, sizeof(a))
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FORD(i,r,l) for (int i=r;i>=l;i--)

const int base = 1e9;
typedef vector<int> BigInt;

void Set(BigInt &a) {
    while (a.size() > 1 && !a.back()) a.pop_back();
}

void Print(BigInt a) {
    Set(a);
    printf("%d", !a.size() ? 0 : a.back());
    for (int i=a.size()-2; i>=0; i--)
        printf("%09d", a[i]); EL;
}

BigInt Integer(string s) {
    BigInt ans;
    if (s[0] == '-') return ans;
    if (!s.size()) {ans.pb(0); return ans;}
    while (s.size()%9 != 0) s = '0'+s;
    for (int i=0;i<s.size();i+=9) {
        int v = 0;
        for (int j=i;j<i+9;j++) v = v*10+(s[j]-'0');
        ans.insert(ans.begin(),v);
    }
    Set(ans);
    return ans;
}

BigInt Integer(char c[]) {
    string s = "";
    FOR(i,0,strlen(c)-1) s = s + c[i];
    return Integer(s);
}

BigInt Integer(ll x) {
    string s = "";
    while (x > 0) s = char(x%10+'0') + s, x /= 10;
    return Integer(s);
}

BigInt Integer(int x) {
    return Integer((ll) x);
}


void operator >> (istream &in, BigInt &a) {
    string s;
    getline(cin, s);
    a = Integer(s);
}
void operator << (ostream &out, BigInt a) {Print(a);}
bool operator < (BigInt a, BigInt b) {
    Set(a), Set(b);
    if (a.size() != b.size()) return (a.size() < b.size());
    FORD(i,a.size()-1,0)
        if (a[i] != b[i]) return (a[i] < b[i]);
    return false;
}

bool operator >  (BigInt a, BigInt b) {return (b < a);}
bool operator == (BigInt a, BigInt b) {return (!(a < b) && !(b < a));}
bool operator <= (BigInt a, BigInt b) {return (a < b || a == b);}
bool operator >= (BigInt a, BigInt b) {return (b < a || b == a);}
bool operator <  (BigInt a, int b) {return (a < Integer(b));}
bool operator >  (BigInt a, int b) {return (a > Integer(b));}
bool operator == (BigInt a, int b) {return (a == Integer(b));}
bool operator >= (BigInt a, int b) {return (a >= Integer(b));}
bool operator <= (BigInt a, int b) {return (a <= Integer(b));}

BigInt max(BigInt a, BigInt b) {return a>b?a:b;}
BigInt min(BigInt a, BigInt b) {return a<b?a:b;}

///Arithmetic Operations
BigInt operator + (BigInt a, BigInt b) {
    Set(a);
    Set(b);
    BigInt ans;
    int carry = 0;
    FOR(i,0,max(a.size(), b.size())-1) {
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        ans.pb(carry%base);
        carry /= base;
    }
    if (carry) ans.pb(carry);
    Set(ans);
    return ans;
}
BigInt operator + (BigInt a, int b) {return a+Integer(b);}
void operator += (BigInt &a, BigInt b){a=a+b;}
void operator += (BigInt &a, int b) {a=a+b;}
void operator ++ (BigInt &a) {a+=1;}

BigInt operator - (BigInt a, BigInt b) {///Here a>b
    Set(a), Set(b);
    BigInt ans;
    int carry=0;
    FOR(i,0,a.size()-1) {
        carry+=a[i]-(i<b.size() ? b[i]:0);
        if (carry<0) ans.pb(carry+base), carry=-1;
        else ans.pb(carry), carry=0;
    }
    Set(ans);
    return ans;
}
BigInt operator - (BigInt a, int b) {return a-Integer(b);}
void operator -= (BigInt &a, BigInt b) {a=a+b;}
void operator -= (BigInt &a, int b) {a=a-b;}
void operator -- (BigInt &a) {a-=1;}

BigInt operator * (BigInt a, BigInt b) {
    Set(a), Set(b);
    BigInt ans;
    ans.assign(a.size()+b.size(), 0);
    FOR(i,0,a.size()-1) {
        ll carry = 0ll;
        for (int j=0;j<b.size() || carry > 0;j++) {
            ll s = ans[i+j] + carry + (ll)a[i]*(j<b.size()?(ll)b[j]:0ll);
            ans[i+j] = s%base;
            carry = s/base;
        }
    }
    Set(ans);
    return ans;
}
BigInt operator *(BigInt a,int b) {return a*Integer(b);}
void operator *= (BigInt &a,BigInt b) {a=a*b;}
void operator *= (BigInt &a,int b) {a=a*b;}

BigInt operator / (BigInt a, BigInt b) {
    Set(a), Set(b);
    if (b==Integer(0)) return Integer("-1");
    BigInt ans, cur;
    FORD(i,a.size()-1,0) {
        cur.insert(cur.begin(), a[i]);
        int x = 0, L = 0, R = base;
        while (L<=R) {
            int mid = (L+R)>>1;
            if (b*Integer(mid) > cur)
                x = mid, R = mid-1;
            else L = mid+1;
        }
        cur = cur - Integer(x-1)*b;
        ans.insert(ans.begin(),x-1);
    }
    Set(ans);
    return ans;
}

BigInt operator / (BigInt a, int b) {
    Set(a);
    BigInt ans;
    ll cur = 0ll;
    FORD(i,a.size()-1,0) {
        cur = (cur*(ll)base + (ll)a[i]);
        ans.insert(ans.begin(),cur/b);
        cur %= b;
    }
    Set(ans);
    return ans;
}

void operator /= (BigInt &a,BigInt b) {a=a/b;}
void operator /= (BigInt &a,   int b) {a=a/b;}



BigInt operator % (BigInt a, BigInt b) {
    Set(a), Set(b);
    if (b==Integer(0)) return Integer("-1");
    BigInt ans;
    FORD(i,a.size()-1,0) {
        ans.insert(ans.begin(), a[i]);
        int x = 0, L = 0, R = base;
        while (L <= R) {
            int mid = (L+R)>>1;
            if (b*Integer(mid)>ans)
                x=mid, R=mid-1;
            else L = mid+1;
        }
        ans = ans - Integer(x-1)*b;
    }
    Set(ans);
    return ans;
}

int operator % (BigInt a, int b) {
    Set(a);
    if (!b) return -1;
    int ans=0;
    FORD(i,a.size()-1,0)
        ans = (ans*(base%b) + a[i]%b)%b;
    return ans;
}
void operator %= (BigInt &a, BigInt b) {a=a%b;}
void operator %= (BigInt &a, int b) {a=a%Integer(b);}

BigInt gcd(BigInt a, BigInt b) {
    Set(a), Set(b);
    while (b>Integer(0)) {
        BigInt r = a%b;
        a=b, b=r;
    }
    Set(a);
    return a;
}
BigInt lcm(BigInt a, BigInt b) {return (a*b/gcd(a,b));}

BigInt sqrt(BigInt a) {
    BigInt x=a, y=(a+1)/2;
    while (y<x)
        x=y, y=(y+a/y)/2;
    return x;
}

BigInt pow(BigInt a, BigInt b) {
    if (b==Integer(0)) return Integer(1);
    BigInt tmp=pow(a, b/2);
    return (!(b%2) ? tmp*tmp:tmp*tmp*a);
}
BigInt pow(BigInt a, int b) {return pow(a,(Integer(b)));}

BigInt pow(BigInt a, BigInt b,BigInt mod) {
    if (b==Integer(0)) return Integer(1);
    BigInt tmp=pow(a, b/2, mod);
    if (!(b%2)) return (tmp*tmp)%mod;
    else return (((tmp*tmp)%mod)*a)%mod;
}

int log(int n, BigInt a) { /// log_n(a)
    Set(a);
    int ans=0;
    while (a>Integer(1)) ans++, a/=n;
    return ans;
}
ll Pow(ll a,ll n,ll M){
    if (n==1) return a;
    ll x=Pow(a,n/2,M);
    x=(x*x)%M;
    if (n&1) x=(x*a)%M;
    return (x*x)%M;
}
int main(){
    ll t,x,y,z;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld %lld %lld",&x,&y,&z);
        BigInt a=Integer(x),b=Integer(y),n=Integer(z);
        M=Integer(1000000007), ab=a-b,ans;
        if (ab==Integer(0))
            ans=(pow(a,n,M)+pow(b,n,M))%M;
        else
            ans=(pow(a,n,ab)+pow(b,n,ab))%M,
            ans=gcd(ans,ab)%M;
        cout<<ans;puts("");
    }
    return 0;
}

//int main(){
//    BigInt B;  cin >> B;
//    BigInt A = Integer("123456789");
//    BigInt C = Integer(123456789ll);
//    int x; x = 123456789;
//
//    if (B<=A)  cout << A - B;
//    else cout << "-"<< B - A;
//
//    cout << A + B; Print(A + x);
//    cout << A * B; Print(A * x);
//    cout << A / B; Print(A / x);
//    cout << A % B; printf("%d\n", A % x);
//
//    ++A, C=A, ++B, C+=B+x;
//    Print(A); Print(B); Print(C);
//
//    cout<<max(A,B); cout<<min(A,B);
//    cout<<gcd(A,B); cout<<lcm(A,B);
//    cout<<sqrt(A);
//    printf("%d %d %d\n", log(2,A), log(10,B), log(5,C));
//
//    A = Integer(16); x = 12;
//    cout << pow(A,B);
//    cout << pow(A,x);
//    return 0;
//}