卢卡斯定理
求(C_m^n~mod~p)
设(m={a_0}^{p_0}+{a_1}^{p_1}+cdots+{a_k}^{p_k},n={b_0}^{p_0}+{b_1}^{p_1}+cdots+{b_k}^{p_k})
则(C_m^nequivprod{C_{a_i}^{b_i}}(mod~p))
扩展卢卡斯定理
好像这也不是什么定理，只是一个计算方法
计算(C_m^n~mod~p)，其中(p={p_1}^{q_1} imes{p_2}^{q_2} imescdots{p_k}^{q_k})时，我们可以先求出(C_m^n~mod~{p_i}^{q_i})，然后用CRT合并。
那么怎么计算(C_m^n~mod~{p_i}^{q_i})呢？
(C_m^n=frac{m!}{n!(m-n)!})，我们只需要算出(m!,{n!}^{-1},{(m-n)!}^{-1})，然后乘在一起。
zjt大爷：(n!)可能在模({p_i}^{q_i})的意义下没有逆元啊，那这就是错的了啊
其实这里求得不是逆元（可能没有逆元），求出来的是(a imes {p_i}^b(gcd(a,p)=1))，前面的(a)用逆元，后面的次数加加减减一下就好了
问题转换成求(n!~mod~p^q)
例如(n=19,p=3,q=2)：
上面这个式子分为四部分：
第一部分：({(1 imes2 imes4 imes5 imes7 imes8)}^2)。这部分的数不超过(p^q)个，可以暴力算
第二部分：(19)。这部分的数不超过(p^q)个，可以暴力算
第三部分：(3^6)。这个在最后处理时求出(m!,n!,(m-n)!)分别有多少个(p)（设为(x,y,z)），则答案要乘上(p^{x-y-z})
第四部分：(1 imes2 imes3 imes4 imes5 imes6)。这个是(lfloorfrac{n}{p} floor!)，可以递归处理