#include using namespace std; #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 Rep(i,a,b) for (int i = a; i < b; ++i) #define rRep(i,a,b) for (int i = a; i > b; --i) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define Bit(x,i) (((x)>>(i))&1) using ll = long long; using vi = vector; using vll = vector; using vvi = vector; using vvll = vector; using vb = vector; using vs = vector; using pii = pair; using pll = pair; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b= mod) x -= mod; return *this; } modint& operator-=(const modint& a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } modint& operator*=(const modint& a) { (x *= a.x) %= mod; return *this; } modint operator+(const modint& a) const { modint res(*this); return res+=a; } modint operator-(const modint& a) const { modint res(*this); return res-=a; } modint operator*(const modint& a) const { modint res(*this); return res*=a; } modint pow(ll t) const { if (!t) return 1; modint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } modint inv() const { return pow(mod-2); } modint& operator/=(const modint& a) { return (*this) *= a.inv(); } modint operator/(const modint& a) const { modint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const modint& m){ os << m.x; return os; } }; const int MAX = 1000010; long long fac[MAX], finv[MAX], inv[MAX]; void NCKinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++) { fac[i] = fac[i - 1] * i % mod; inv[i] = mod - inv[mod%i] * (mod / i) % mod; finv[i] = finv[i - 1] * inv[i] % mod; } } long long NCK(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % mod) % mod; } ll powmod(ll n, ll p, ll m) { if(p == 0) return 1; ll res = powmod(n, p/2, m); n %= m; if(p%2 == 0) return (res*res) % m; return (((res*res) % m)*n) % m; } int main() { ll N, K, M; cin >> N >> K >> M; modint ans = 0; if(M == 1) { ans += powmod(N, N-1, mod); Rep(i, 2, min(N, K+1)+1) { // ちょうどループ if(K%i != 0) continue; modint tmp = fac[i-2]; tmp *= NCK(N-2, i-2); if(i-2 == 0) tmp = 1; tmp *= powmod(N, N-i, mod); ans += tmp; } cout << ans << endl; return 0; } NCKinit(); Rep(i, 2, min(N, K+1)+1) { // ちょうどループ if(K%i != 0) { modint tmp = fac[i-2]; tmp *= NCK(N-2, i-2); if(i-2 == 0) tmp = 1; tmp *= powmod(N, N-i, mod); ans += tmp; } // ほか modint tmp = fac[i-2]; tmp *= NCK(N-2, i-2); if(i-2 == 0) tmp = 1; tmp *= i-1; tmp *= powmod(N, N-i, mod); ans += tmp; } cout << ans << endl; }