No.117

$$\begin{align*} C(n, k) &= \frac{n!}{k!(n-k)!} \\ P(n, k) &= \frac{n!}{(n-k)!} \\ H(n, k) &= C(n+k-1, k) \\ &= \frac{(n+k-1)!}{k!(n-1)!} \end{align*}$$

である. ここで $p = 10^9 + 7$ とすると, $p$ は素数であるので剰余環 $\mathbb{Z}/p\mathbb{Z}$ の要素には逆元が存在し, その値は拡張ユークリッドの互除法で計算することができる.

ここで剰余環 $\mathbb{Z}/p\mathbb{Z}$ 上で $n!$ およびその逆元をあらかじめ求めておけば, 上記の計算はすべて $O(1)$ で可能である.