이항 계수 4

#include <bits/stdc++.h>

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

ll n, r, mod;
ll dp[MAX_N][MAX_N];

vector<ll> kRadix(ll n, ll k) {
    vector<ll> radix;
    while(n) {
        radix.push_back(n % k);
        n /= k;
    }
    return radix;
}

ll comb(ll n, ll r) {
    if(n < r) return 0;
    if(n / 2 < r) r = n - r;

    ll& res = dp[n][r];
    if(res != -1) return res;
    if(r == 0) return res = 1;
    if(r == 1) return res = n;
    return res = (comb(n - 1, r - 1) + comb(n - 1, r)) % mod;
}

ll solve() {
    auto N = kRadix(n, mod);
    auto R = kRadix(r, mod);

    ll res = 1, mi = min(N.size(), R.size());

    for(ll i = 0; i < mi; i++) {
        res = res * comb(N[i], R[i]) % mod;
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp,-1,sizeof(dp));
    cin >> n >> r >> mod;

    cout<<solve();
    return 0;
}