#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rep(i, n) repr(i, 0, n) #define INF 2e9 #define MOD 1000000007 //#define MOD 998244353 #define LINF (long long)4e18 #define jck 3.141592 const double EPS = 1e-10; using ll = long long; using Pi = pair; using Pl = pair; template struct Mat{ vector> val; Mat(int n, int m, T x = 0) : val(n,vector(m,x)){} void init(int n, int m, T x = 0){ val.assign(n,vector(m,x)); } size_t size(){ return val.size(); } inline vector& operator [](int i){ return val[i]; } }; Mat operator *(Mat A, Mat B){ Mat R(A.size(),B[0].size()); for(int i = 0; i < A.size(); i++){ for(int j = 0; j < B[0].size(); j++){ for(int k = 0; k < B.size(); k++){ R[i][j] += A[i][k]*B[k][j]+MOD; R[i][j] %= MOD; } } } return R; } Mat pow(Mat A, ll n){ Mat R(A.size(),A.size()); for(int i = 0; i < A.size(); i++) R[i][i] = 1; while(n > 0){ if(n&1) R = R*A; A = A*A; n >>= 1; } return R; } int main(){ ll a,b,n; cin >> a >> b >> n; Mat mat(2,2); mat[0][0] = a; mat[0][1] = b; mat[1][0] = 1; Mat mat2 = pow(mat,n); cout << mat2[1][0] << endl; }