参自： http://www.cnblogs.com/liziran/p/6804803.html
https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86/4776158?fr=aladdin

现在目标是求Cnm%p，p为素数（经典p=1e9+7）
虽然有Cnm=n!m!(n−m)!，但由于取模的性质对于除法不适用，所以Cnm%p≠(n!%pm!%p∗(n−m)!%p)%p 所以需要把“除法”转换成“乘法”，才能借助取模的性质在不爆long long的情况下计算组合数。这时候就需要用到“逆元”！ 逆元：对于a和p，若a*b%p≡1，则称b为a%p的逆元。 那这个逆元有什么用呢？试想一下求(ab)%p，如果你知道b%p的逆元是c，那么就可以转变成(ab)%p = a*c%p = (a%p)(c%p)%p 那怎么求逆元呢？这时候就要引入强大的费马小定理！ 费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p），即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。 接着因为ap−1 = ap−2∗a，所以有ap−2∗a%p≡1！对比逆元的定义可得，ap−2是a的逆元！ 所以问题就转换成求解ap−2，即变成求快速幂的问题了（当然这需要满足p为素数）。 现在总结一下求解Cnm%p的步骤：

1. 通过循环，预先算好所有小于max_number的阶乘（%p）的结果，存到fac[max_number]里 (fac[i] = i!%p)
2. 求m!%p的逆元（即求fac[m]的逆元）：根据费马小定理，x%p的逆元为xp−2，因此通过快速幂，求解fac[m]p−2%p，记为M
3. 求(n-m)!%p的逆元：同理为求解