模闆——Lucas（大組合數取模）

#include<iostream>
using namespace std;

typedef long long ll;
const int maxn = 1e6 + 7;


ll n, m, p;
ll fac[maxn];

void init_fac() {		//階乘打表
	fac[0] = 1;
	for (ll i = 1; i <= p; i++) {
		fac[i] = (fac[i - 1] * i) % p;
	}
}
ll quick_pow(ll a, ll b) {		//a的逆元pow(a, p - 2)  p為質數
	ll ans = 1;
	while (b) {
		if (b & 1) {
			ans = (ans * a) % p;
		}
		a = (a * a) % p;
		b >>= 1;
	}
	return ans;
}
ll C(ll n, ll m) {		//求1e6以内的組合數的正常方法
	if (n < m) return 0;		//特判一下n < m的情況
	ll up = fac[n];
	ll down = fac[n - m] * fac[m] % p;
	down = quick_pow(down, p - 2);		//求分母的逆元
	ll ans = up * down % p;		//傳回C(n, m)
	return ans;
}
ll Lucas(ll n, ll m) {		//記闆子吧！！！不好推導
	if (m == 0) return 1;
	else return Lucas(n / p, m / p) * C(n % p, m % p) % p;
}
int main() {

	cin >> n >> m >> p;
	init_fac();		//階乘打表

	cout << Lucas(n, m) << endl;
	return 0;
}