No.109 N! mod M

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 44
作問者 : antaanta
3 ProblemId : 120 / 出題時の順位表

問題文

$N! \bmod M$を求めよ。

入力

$T$
$N_1 M_1$
$\vdots$
$N_T M_T$

入力は複数のテストケースからなる。 1行目に、テストケース数を表す整数$T$が与えられる。 2行目以降、各テストケースが与えられる。

  • $1 \le T \le 100$
  • $1 \le M \le 10^9$
  • $\max(0, M_i - 10^5) \le N_i \le 10^9$

出力

各テストケース$i (1 \le i \le T)$に対し、$N_i!$を$M_i$で割った余りを1行に出力し、改行せよ。

サンプル

サンプル1
入力
4
0 2
5 100
999999936 999999937
1000000000 1
出力
1
20
999999936
0
  1. $0! = 1$
  2. $5! = 120$であり、100で余りを取った20が答えとなる。
  3. $999999936! \equiv 999999936 \pmod {999999937}$である。
  4. 1で割った余りはどんな数であれ0になる。
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。