フェルマーの小定理について

フェルマーの小定理とは、 ${p}$ が素数のとき、以下が成り立つことである。

${ \displaystyle \begin{eqnarray} a^{p-1} = 1 \bmod p \end{eqnarray} }$

ここから、以下が言える。

${ \displaystyle \begin{eqnarray} a^{p-2} = a^{-1} \bmod p \end{eqnarray} }$

これはつまり、 ${p}$ が素数ならば、ある数 $\frac{n}{a}$ を ${p}$ で割った余りは、 ${n * a^{p-2}}$ を ${p}$ で割った余りに等しいということ。

combinationを計算するときに活かせるフェルマーの小定理

今後活かせるタイミングは、combinationを計算した結果を素数（1000000007など）で割った結果を求めろと言われたとき。

mod pの世界では、数 ${a}$ で割るということは ${a^{p - 2}}$ をかけることに等しい。

今回の問題は ${ \displaystyle \dfrac {(H + W - 2)!}{(H - 1)! (W-1)!} }$ を1000000007で割った余りが答え。

まず分子については、1000000007で割った値をループを回してかけていけばよい。

分母についてはフェルマーの小定理の変形バージョンにより、各数の ${p-2}$ 乗を ${p}$ で割った余りを、ループを回してかけあわせていけばよい。

けんちょんさん本当にいつもありがとうございます…！