AT_pakencamp_2024_day3_1_l k!

$ T $ 個のテストケースについて、以下の問題に答えてください。 正整数 $ N $ 及び素数 $ P $ が与えられます。 $ \displaystyle\prod_{k=1}^N k! $ を $ P $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ P $

各テストケースについて、改行区切りで答えを出力せよ。

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