問題文

T 個のテストケースについて、以下の問題に答えてください。

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

制約

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

部分点

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

入力例 1

3
3 998244353
1 1000000007
100 998244353

出力例 1

12
1
26505319

1 つ目のケースについて、\displaystyle\prod_{k=1}^3 k!=1 \times 2 \times 6=12 なので、998244353 で割った余りは 12 です。