注意:この問題の実行時間制限は $1$ ケース当たり $10$ 秒です。

問題文

正整数 $T$, $M$ が与えられます。 その後、$T$ 個のテストケースが与えられるので、それぞれについて次の問題の答えを求めてください。

$(1,2,...,N)$ の順列 $P$ に対して、スコア $f(P)$ を以下に示す操作を 0 回以上繰り返して得られる、相異なる順列の個数とします。

以下、順列 $P$ の $i \,(1 \leq i \leq N)$ 番目の要素を $P_{i}$ とします。

• 各操作では、次の 2 個の処理のうちどちらかを 1 つ選び行います。

  • $P$ を、すべての $i = 1,2,...,N$ に対して $P_{R_i} = i$ を満たす $(1,2,...,N)$ の順列 $R$ で置き換える。
  • $P$ を、すべての $i = 1,2,...,N$ に対して $R_{i} = P_{N - i + 1}$ を満たす $(1,2,...,N)$ の順列 $R$ で置き換える。

$(1,2,...,N)$ の順列 $P$ としてあり得るものは $N!$ 通りありますが、それらのスコア $f(P)$ の総和を $M$ で割ったあまりを求めてください。

制約

• $1 \leq T \leq 10^6$
• $1 \leq N \leq 5 \times 10^6$
• $1 \leq M \leq 10^9$
• 入力はすべて整数

入力

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

$T$ $M$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

ここで、$\mathrm{case}_i$ は $i$ 番目のテストケースを表します。

各テストケースは以下の形式で与えられます。

$N$

出力

答えを $T$ 行に渡って出力してください。

$i \,(1 \leq i \leq T)$ 行目には、$i$ 番目のテストケースに対する答えを出力してください。

サンプル

3 998244353
3
1
4478429

20
1
722594001