No.109

$N \geq M$ ならば答えは 0 である.

$N \leq 10^5$ ならば愚直に計算する.

$N \gt 10^5$ のときは以下のように計算する.

$M$ が素数のとき:

ウィルソンの定理

$$(M-1)! \equiv M-1 \pmod M$$

を使う.

$$N! = \frac{(M-1)!}{(M-1)(M-2)\cdots(N+1)}$$

であり, $M - N \leq 10^5$ の制限があるので, $M-1, M-2, \dots, N+1$ の逆元を求めて計算すればいい.

$M$ が合成数のとき:

$M$ の最小の素因数を $p$ とすると,

$$(M/p)! \equiv 0 \pmod M$$

となるので, $N \geq M/p$ ならは答えは 0 である.

$N \lt M/p$ の場合は,

$$M - 10^5 \leq N \lt M/p \Longrightarrow M \lt 10^5 \cdot \frac{p}{p - 1}$$

となるので, 愚直に計算すればいい.