High School Maths

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

//#define ll long long int
typedef long long  ll;
//#define LD long long double
ll mod =1e9+9;
ll add(ll a,ll b){
  ll x= a+b;
  if(x>=mod){
    x-=mod;
  }
  return x;
}
ll sub(ll a,ll b){
  ll x= a-b;
  if(x<0){
    x+=mod;
  }
  return x;
}
ll mul(ll a, ll b) {
  return (a * b % mod);
}
ll binary_exponentation(ll a,ll n,ll mod ){
	ll ans =1;
	while(n){
	   if(n%2==1){
	      ans=(ans*a)%mod;
	   }
	   a=a*a %mod;
	   n/=2;
	}
	return ans;
}
signed main( ){
    IOS
    int t;cin>>t;
    while(t--){
      ll a,b,n,ans;
      cin>>a>>b>>n;
      if(a==1){
          n %= mod;
        ans=(b*n)%mod;
        ans+=1;
      }
      if(a > 1){
        ll x=binary_exponentation(a,n,mod);
        ll y = binary_exponentation(a-1,mod-2,mod);
        ans = mul(x-1,y);
        //cout <<ans<<endl;
        ll z= a+b-1;
        ans = mul(ans,z);
        //cout <<ans<<endl;
        ans = add(ans,1);
        //cout <<ans<<endl;

      }
      cout<<ans%mod<<"\n";
      
    }
    return 0;
}