-
求：(inom{n}{m} ~mod~p^k)
-
(n,mle 10^{18})，(p^kle 10^7)。
我们可以求出这样一个形式，即(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))
洛谷模板题：
https://www.luogu.org/problemnew/show/P4720
优化：
高斯泛化的威尔逊定理
也就是(p^k)时的威尔逊定理。
也就是说：
(prod_{i=1且i~mod~p>0}^{p^k}~~i)只能是(1)或者(-1)，那么可以省去快速幂的复杂度。
复杂度就变成了(O(log_p^n+p^k))