#include using namespace std; #define DBG cerr << '!' << endl; #define REP(i,n) for(ll (i) = (0);(i) < (n);++i) #define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i) #define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i)) #define PB push_back #define MP make_pair #define FI first #define SE second #define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;} #define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;} #define ALL(v) v.begin(),v.end() #define Decimal fixed< struct ModInt { static const int Mod = MOD; unsigned x; ModInt() : x(0) { } ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; } ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; } int get() const { return (int)x; } ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; } ModInt &operator/=(ModInt that) { return *this *= that.inverse(); } ModInt operator+(ModInt that) const { return ModInt(*this) += that; } ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } return ModInt(u); } bool operator==(ModInt that) const { return x == that.x; } bool operator!=(ModInt that) const { return x != that.x; } ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; } }; template ostream& operator<<(ostream& st, const ModInt a) { st << a.get(); return st; }; template ModInt operator^(ModInt a, unsigned long long k) { ModInt r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; } typedef ModInt<1000000007> mint; typedef long long ll; typedef pair P; ll f(ll a,ll b){ ll tmp = a; ll ret = 1; REP(i,60){ if(b & (1LL<> B >> C >> d; B %= 1000000007; if(C == 1){ d %= 1000000007; cout << (B*d)%1000000007 << endl; return 0; } C %= 1000000007; mint b(B*C); mint c(C-1); b /= c; b *= (f(C,d) - 1); cout << b << endl; return 0; }