以下のゲームを考えます。
| 数直線上で座標が正整数であるような相異なる \(N\) 点に石が \(1\) 個ずつ置かれています。 最初、\(i\) 個目の石は座標 \(X_i\) に置かれています。 \(2\) 人のプレイヤーがゲームをします。 先手と後手が交互に以下の操作を繰り返し、操作を行えなくなった方の負けです。 |
|
このゲームは有限回の操作で終了することが証明できます。 以下の条件を満たす正整数列 \(X\) の個数を \(998244353\) で割った余りを求めてください。
\(1\) つの入力につき \(T\) 個のテストケースが与えられるので、それぞれについて解いてください。
入力は以下の形式で標準入力から与えられます。
| \(T\) | |
| \(\mathrm{case}_{1}\) | |
| \(\mathrm{case}_{2}\) | |
| \(\vdots\) | |
| \(\mathrm{case}_{T}\) |
\(t\) 番目のテストケース \(\mathrm{case}_t\) は以下の形式で与えられます。
| \(N~S\) |
入力は以下の制約をすべて満たします。
\(T\) 行出力してください。
\(t\) 行目に \(\mathrm{case}_t\) に対する答えを出力してください。
以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。
71 82 83 84 83 292 1004 1000000000000000000
1 6 12 0 336 98 990355765