给定 $n,m,p$，求出 $(^n_m)\mod p$ 的值。

你可以认为 $0 \le m\le n$。

前面省略 $512$ 种简单求法。

$n,m\le 10^{18}$，$p\le 10^6$

这个用 exlucas 即可，时间复杂度 $O(p\log p)$ 左右，应该不能做到更优了。

$m\le 10^6$，$n\le 10^{18}$，$p\le 10^{18}$

考虑 $1$ 到 $m$ 中的质数是否是 $p$ 的因数。

如果是的话，可以考虑记录每种质数在 $m!$ 里的出现次数和在 $\frac{n!}{(n-m)!}$ 的出现次数，这就和 exlucas 有点像了。

然后因为这种质数 $t$ 不超过 $\omega(p)$（？） 个，所以可以直接枚举 $t^k$，计算出现次数。

剩下的因为和 $p$ 互质，所以可以直接全部乘起来 exgcd。

然后这样是 $O(m+\omega(p)\log n)$ 的。

$n,m,p\le 10^{18}$

这玩意看起来就不能做。

于是组合数在 $m$ 比较小或 $p$ 比较小的时候都能做。