AT_pakencamp_2024_day3_2_l k^k

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

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

答えを出力せよ。

### 部分点 - $ N \leq 10^6 $ を満たすデータセットに正解した場合は、 $ 10 $ 点与えられる。 - 追加制約のないデータセットに正解した場合は、上記とは別に $ 90 $ 点与えられる。 ### Sample Explanation 1 $ \displaystyle\prod_{k=1}^3 k^k=1 \times 4 \times 27=108 $ なので、 $ 998244353 $ で割った余りは $ 108 $ です。 ### Constraints - $ 1 \leq N \leq 10^8 $ - $ 2 \leq P \leq 10^9+9 $ - $ P $ は素数 - 入力は全て整数