lucas定理
引入
给定(n,m,p)，求(xequiv C^n_m (mod p))的值
老师，我会阶乘爆算！
(1 leq n,m leq 10^{10},1 leq p leq 10^5,p为质数)
……
什么是lucas定理
对于(C^n_m \% p)，且p为质数，以下式子成立：
设(n=sp+q,m=vp+r)
则(C^n_m \% p = C^s_v imes C^q_r \% p)
或者不严谨地记作(C^n_m \% p = C^{n/p}_{m/p} imes C^{n \% p}_{m \% p} \% p)