#include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)< P; typedef pair pll; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector vvl; typedef vector vd; typedef vector

vp; typedef vector vs; const int MAX_N = 100005; template class mat : public vector > { public: int r, c; //行,列 mat(int n, int m) : r(n), c(m){ for(int i = 0; i < r; i++){ this->push_back(vector(c,0)); } } mat operator*(const mat& that){ mat X(this->r, that.c); for(int i = 0; i < this->r; i++){ for(int k = 0; k < this->c; k++){ for(int j = 0; j < that.c; j++){ X[i][j] = (X[i][j] + (*this)[i][k]*that[k][j]) % MOD; } } } return X; } void print(){ for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ cout << this[i][j] << ","; } cout << this[i][c-1] << endl; } } }; template mat mod_pow(mat A,ll cnt) { int n = A.r; mat B(n,n); for(int i = 0; i < n; i++){ B[i][i] = 1; } while(cnt>0){ if(cnt & 1){ B = B*A; } A = A*A; cnt >>= 1; } return B; } // 第1引数 : A[n] = a[0] + a[1] * A[n-k] + a[2] * A[n-k+1] + ... + a[k] * A[n-1] // 第2引数 : A[0] = x[0], A[1] = x[1], ... , A[k-1] = x[k-1] template T solve(vector& a, vector& x, ll n) { int k = (int)a.size() - 1; if(n < k){ return x[n]; } mat A(k+1,k+1); rep(i,k+1){ A[0][i] = a[k-i]; } rep(i,k-1){ A[i+1][i] = 1; } A[k][k] = 1; mat B = mod_pow(A,n-k+1); T res = 0; rep(i,k){ res = (res + B[0][i]*x[k-1-i]%MOD) % MOD; } res = (res + B[0][k]) % MOD; return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); ll b,c,d; cin >> b >> c >> d; b %= MOD, c %= MOD; vl a = {b*c%MOD,c}, x = {0}; cout << solve(a,x,d) << "\n"; return 0; }