#include <bits/stdc++.h>
typedef long long ll;

const ll mod = 1e9 + 7;

ll mul(ll x,ll y,ll p) {
	ll ans = 0;
	for(;y;y >>= 1) {
		if(y & 1)(ans += x) %= p;
		(x += x) %= p;
	}
	return ans;
}

ll power(ll x,ll y,ll p) {
	ll ans = 1;
	for(;y;y >>= 1) {
		if(y & 1)ans = mul(ans , x , p);
		x = mul(x , x , p);
	}
	return ans;
}

ll gcd(ll x,ll y) {
	return y ? gcd(y , x % y) : x;
}

void work() {
	ll a,b,n;
	scanf("%lld %lld %lld",&a,&b,&n);
	if(a == b)printf("%lld\n",(power(a , n , mod) + power(b , n , mod)) % mod);
	else printf("%lld\n",gcd((power(a , n , a - b) + power(b , n , a - b)) % (a - b) , a - b) % mod);
	return ;
}

int main() {
	freopen("gcmod.in","r",stdin);
	freopen("gcmod.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T --)work(); 
	return 0;
}