L - k^k Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

正整数 N 及び素数 P が与えられます。\displaystyle\prod_{k=1}^N k^k を P で割った余りを求めてください。

制約

  • 1 \leq N \leq 10^8
  • 2 \leq P \leq 10^9+9
  • P は素数
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N P

部分点

  • N \leq 10^6 を満たすデータセットに正解した場合は、10 点与えられる。
  • 追加制約のないデータセットに正解した場合は、上記とは別に 90 点与えられる。

出力

答えを出力せよ。

入力例 1

3 998244353

出力例 1

108

\displaystyle\prod_{k=1}^3 k^k=1 \times 4 \times 27=108 なので、998244353 で割った余りは 108 です。

入力例 2

1 1000000007

出力例 2

1

入力例 3

100 998244353

出力例 3

598189773