#include #include using namespace atcoder; using mint = modint1000000007; using namespace std; #define ll long long #define rep(i, N) for(ll i = 0; i < N; i++) // /* ACL版:NTT可能なmodintで使用する */ // #include // using namespace atcoder; // template // vector multiply(const vector& a, const vector& b) { // return atcoder::convolution(a, b); // } /* 愚直版:ACLの畳み込みが使えない型で使用する */ template vector multiply(const vector& a, const vector& b) { if (a.empty() || b.empty()) return {}; vector c(a.size() + b.size() - 1); for (size_t i = 0; i < a.size(); ++i) { for (size_t j = 0; j < b.size(); ++j) { c[i + j] += a[i] * b[j]; } } return c; } /** * 母関数A(x) = P(x) / Q(x) の x^n の係数を返す * 計算量 O(M(d) log n) * d := deg(Q) * M(d) := 次数 d の多項式同士の畳み込みにかかる計算量 */ template T bostan_mori( vector p, vector q, unsigned long long n ) { assert(!q.empty() && q[0] != T{}); while (!p.empty() && p.back() == T{}) p.pop_back(); assert(p.size() < q.size()); const size_t d = q.size(); p.resize(d - 1); while (n != 0) { vector q_neg = q; for (size_t i = 1; i < q_neg.size(); i += 2) { q_neg[i] = -q_neg[i]; } auto pq = multiply(p, q_neg); auto qq = multiply(q, q_neg); vector next_p(d - 1); vector next_q(d); const size_t parity = static_cast(n & 1ULL); for (size_t i = 0; i < next_p.size(); ++i) { if (2 * i + parity < pq.size()) next_p[i] = pq[2 * i + parity]; } for (size_t i = 0; i < next_q.size(); ++i) { if (2 * i < qq.size()) next_q[i] = qq[2 * i]; } p = move(next_p); q = move(next_q); n >>= 1; } return p.empty() ? T{} : p[0] / q[0]; } int main(void) { ll A,B,N; cin>>A>>B>>N; vectorP={0,1},Q={1,-A,-B}; cout<