#include #include using namespace std; using mint = atcoder::modint1000000007; void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } mint fac[1 << 20], inv[1 << 20]; void init() { fac[0] = 1; for (int i = 1; i < (1 << 20); i++) { fac[i] = fac[i - 1] * i; } inv[(1 << 20) - 1] = fac[(1 << 20) - 1].inv(); for (int i = (1 << 20) - 2; i >= 0; i--) { inv[i] = inv[i + 1] * (i + 1); } } mint binom(int n, int k) { return fac[n] * inv[k] * inv[n - k]; } mint perm(int n, int k) { return fac[n] * inv[n - k]; } int main() { fast_io(); init(); int n, m; long long k; cin >> n >> m >> k; mint ans = 0; for (int i = 1; i <= n; i++) { if (k % i == 0) { ans += perm(n - 1, i - 1) * mint(n).pow(n - i); } } if (m != 1) { ans = mint(n).pow(n) - ans; ans /= (n - 1); } cout << ans.val() << endl; }