突然想起多项式科技能做个快速求阶乘。

那在 $p$ 为质数且 $n<=p$的时候可以直接求 $n!$、 $m!$ 和 $(n-m)!$，然后取个逆就行了。

所以可以做到 $O(\sqrt{n}\log n)$ 或在 $n>p$ 时用 lucas 做到 $O(\sqrt{p}\log^2 p)$，如果用 exlucas 应该可以做到 $O(\sqrt{p}\log^2 p)$，但是常数因为是任意模数所以很大。

如果 $p$ 是给定的用分段打表阶乘可以做到自己跑 $O(n)$ 时间，然后写出一个 $O(\frac n B)$ 的做法，考虑一般代码最多 $50000$ 字符，大约压缩一下能塞 $10^4$ 个数进去，也就是可以做到 $O(\frac n {10^4})$。