이항 계수 5

#include <bits/stdc++.h>

#define MAX_N 4000001
#define ll long long
using namespace std;

ll n, k, mod;
bool sieve[MAX_N] {1,1};

ll modpow(int x, int p) {
    if(p == 1) return x;
    if(p == 0) return 1;

    ll res = modpow(x, p>>1);
    res = (res * res) % mod;
    if(p & 1) res = (res * x) % mod;
    return res;
}

ll solve() {
    ll res = 1;
    for(ll i = 2; i <= n and res; i++) {
        if(sieve[i]) continue;
        
        for(ll j = i * i; j <= n; j += i)
            sieve[j] = true;

        ll c = 0;

        for(ll j = i; j <= n; j *= i) {
            c += (n / j) - (k / j) - ((n - k) / j);
        }

        res = res * modpow(i, c) % mod;
    }

    return res;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> mod;
    cout<<solve();
    return 0;
}