#include <iostream> #include <vector> using namespace std; typedef long long ll; typedef vector<vector<ll>> vvl; ll n,mod = 1000000007; vvl mul(const vvl &a,const vvl &b){ vvl c(n,vector<ll>(n,0)); int i,j,k; for(i=0;i<n;i++){ for(j=0;j<n;j++){ ll x = 0; for(k=0;k<n;k++){ (x += a[i][k]*b[k][j]) %= mod; } c[i][j] = x; } } return c; } vvl pw(const vvl &a, ll x){ vvl ret(n,vector<ll>(n,0)),b(n,vector<ll>(n,0)); int i,j,k; for(i=0;i<n;i++){ ret[i][i] = 1; } for(i=0;i<n;i++){ for(j=0;j<n;j++){ b[i][j] = a[i][j]; } } while(x){ while(!(x&1)){ b = mul(b,b); x /= 2; } ret = mul(ret,b); x--; } return ret; } vector<ll> mul2(const vvl &a, const vector<ll> &b){ vector<ll> c(n,0); int i,j; for(i=0;i<n;i++){ ll x = 0; for(j=0;j<n;j++){ (x += a[i][j]*b[j]) %= mod; } c[i] = x; } return c; } int main(){ long long a,b,x; cin >> a >> b >> x; n = 2; vector<ll> v(2,0); v[0] = 1; vvl m(2,vector<ll>(2,0)); m[0][0] = a; m[0][1] = b; m[1][0] = 1; m = pw(m,x); cout << mul2(m,v)[1] << endl; }