扩展Lucas定理及其优化

我们可以求出这样一个形式，即(n!=p^{x}*y(gcd(y,p)=1))，然后：
(inom{n}{m}={n! over m!*(n-m)!})

这样(p)的幂次用上面-下面算，然后(y)是有逆元的，逆元的话可以用欧拉定理，如果写的是excrt，也可以直接用，这样就做完了。

现在算(n!)：

(n!=(prod_{i=1且i~mod~p>0}^{p^k}i)^{n/{p^k}}*(prod_{i=1且i~mod~p>0}^{n~mod~p^k}i)*(n/p)!*p^{n/p})

((n/p)!)可能产生新的(p)的倍数，这个可以递归解决。

要预处理(p^k)的与(p)互质数的前缀积，每一层还有个快速幂，复杂度：(O(log_p^n *log_2^n+p^k))

也就是(p^k)时的威尔逊定理。

也就是说：
(prod_{i=1且i~mod~p>0}^{p^k}~~i)只能是(1)或者(-1)，那么可以省去快速幂的复杂度。

复杂度就变成了(O(log_p^n+p^k))