#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define nl cout<<endl

#define pii pair<ll,ll>
#define vi  vector<ll>
#define vii vector<pii>
#define mi  map<ll,ll>
#define all(a)  (a).begin(),(a).end()

#define pb push_back
#define make make_pair
#define ff first
#define ss second
#define hell 1000000007

#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;
#define N 3
ll add(ll a,ll b)
{
	return (a%hell +b%hell)%hell;
}
ll mult(ll a,ll b)
{
	return (a%hell * b%hell)%hell;
}
ll powerr(ll a,ll b,ll m)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%m;
        b/=2;
        a=(a*a)%m;
    }
    return ans%hell;
}
struct matrix
{
	ll arr[N][N];
	void reset()
	{
		memset(arr,0,sizeof(arr));
	}
	void identity()
	{
		rep(i,0,N)
		arr[i][i]=1;
	}	
	matrix operator +(const matrix &o) const
	{
		matrix res;
		rep(i,0,N)
		{
			rep(j,0,N)
			res.arr[i][j]=add(arr[i][j],o.arr[i][j]);
		}
		return res;
	}
	matrix operator *(const matrix &o) const
	{
		matrix res;
		rep(i,0,N)
		{
			rep(j,0,N)
			{
				res.arr[i][j]=0;
				rep(k,0,N)
				{
					res.arr[i][j]=add(res.arr[i][j],mult(arr[i][k],o.arr[k][j]));
				}
			}
		}
		return res;	
	}
};
ll gcd(ll a,ll b)
{
    if(a==0)
        return b;
    else
        return gcd(b%a,a);
}
matrix power(matrix arr,ll x)
{
	matrix res;
	res.reset();
	res.identity();
	while(x)
	{
		if(x&1)
		res=res*arr;

		arr=arr*arr;
		x>>=1;
	}
	return res;
}
ll fib(ll n)
{
	if(n<=2)
	return n;

	n-=2;
	matrix a;
	a.reset();
	a.arr[0][0]=1;
	a.arr[0][1]=1;
	a.arr[1][0]=1;
	a.arr[1][1]=0;


	matrix expo;
	expo.reset();
	expo=power(a,n);	

	ll ans=(2*(expo.arr[0][0])%hell)%hell + (expo.arr[0][1])%hell;
	ans%=hell;
	return ans;
}
int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
        
	ll t;cin>>t;
	while(t--)
	{
		ll p,q,n;cin>>p>>q>>n;
		n++;
		if(n==1)
		{
			cout<<p<<endl;
			continue;
		}
		if(n==2)
		{
			cout<<q<<endl;
			continue;
		}
		if(n==3)
		{
			cout<<(p+q+(p*q)%hell)%hell<<endl;
			continue;
		}

		ll t1=(1+p)%hell;
		ll t2=(1+q)%hell;

		ll n1=n-3;ll n2=n-2;

		ll val1=fib(n1)%hell;
		ll val2=fib(n2)%hell;

		val1=powerr(t1,val1,hell)%hell;
		val2=powerr(t2,val2,hell)%hell;

		ll ans=(val1*val2)%hell;
		ans=(ans-1+hell)%hell;
		cout<<ans<<endl;
	}
}