hdu 4869 费马小定理+快速幂 解决C(m,k) %mod

C(m,k)=m!/(k!*(m-k)!)    对C(m,k)取模mod

取模运算规则：

1. (a + b) % p = (a % p + b % p) % p （1）
2. (a - b) % p = (a % p - b % p) % p （2）
3. (a * b) % p = (a % p * b % p) % p （3）
4. a ^ b % p = ((a % p)^b) % p （4）

在求 m!/(k!*(m-k)!)的时候由于有除法不能像以上那样一步取模一次，因此我们想到了用费马小定理把分母转化成整数再用第三条求模。

费马小定理：假如a是整数，p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1。

                 那么a^(p-1)/a = 1/a%p 得到1/a%p= a^(p-2) ,  将一个分数的值化成了整数

  因此在求以上令a=k!*(m-k)!   ,   p=mod(即mod=1000000009)，

  1/(k!*(m-k)!)  %mod= (k!*(m-k)!)^(mod-2)