#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
const int mod=1e9+7; 
ll qm(ll a,ll n,ll m); //取模m的a^n 
ll gcd(ll m,ll n);    //gcd(m,n)
int main()
{
	freopen("gcmod.in","r",stdin);
	freopen("gcmod.out","w",stdout);
	
	int T;
	cin>>T;
	
	ll A,B,N,d;
	while(T>0&&scanf("%lld%lld%lld",&A,&B,&N))
	{
		T--;

		d=abs(A-B);
		
		if(d==0)
		  cout<<(qm(A,N,mod)+qm(B,N,mod))%mod;
		else
		{
			A%=d;
			B%=d;
			
			cout<<gcd(((qm(A,N,d))+qm(B,N,d)),d)%mod;
		}  
    }
	return 0;	  
}
ll qm(ll a,ll n,ll m)
{
	if(n==1)
	  return a;
	else
	{
		a%=m;
		ll base=qm(a,n/2,m)%m;
		ll temp=(base*base)%m;
		return ((n%2==0?1:a)*temp)%m;
	}	
}
ll gcd(ll m,ll n)
{
	return n==0?m:gcd(n,m%n);
}