nCk_prime_power.cpp

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Min(a,b) (a<=b)? a : b

/* This function calculates power of p in n! */
ll fact(ll n, ll p)
{
    ll k = 0;
    while (n > 0)
    {
        k += n/p;
        n /= p;
    }
    return k;
}

/* This function calculates (a^b)%MOD */
ll modPow(ll a, ll b, ll MOD)
{
    ll x = 1, y = a;
    while(b > 0)
    {
        if(b%2 == 1)
        {
            x = (x*y);
            if(x > MOD) x %= MOD;
        }
        y = (y * y);
        if(y > MOD) y %= MOD;
        b /= 2;
    }
    return x;
}

ll nCr(ll n, ll r, ll MOD)
{
    ll res = 1;
    vector<bool> isPrime(n+1,1);
    for(ll i = 2; i <= n; i++)
        if(isPrime[i])
        {
            for(ll j = 2*i; j <= n; j += i)
                isPrime[j]=0;
            ll power = fact(n,i) - fact(r,i) - fact(n-r,i);
            res = (res * modPow(i, power, MOD)) % MOD;
        }
    return res;
}

int main()
{
    ll n,r,m;
    while (cin >> n >> r >> m)
    {
        cout << nCr(n, r, m) << endl;
    }
    return 0;
}