AT_abc463_g [ABC463G] Random Walk Distance

正整数 $ N $ および整数 $ X $ が与えられます。 高橋君が数直線上の座標 $ 0 $ にいます。 高橋君はこれから $ N $ 回、以下の移動を行います。 - 座標 $ x $ にいるとき、座標 $ x-1 $ または座標 $ x+1 $ のどちらかを等確率で選び、そこに移動する。 ただし $ N $ 回の移動での移動先の選択はすべて独立です。 $ N $ 回の移動を全て終えた後の座標を $ x' $ とします。 $ |x'-X| $ の期待値を $ \bmod{998244353} $ で求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 期待値 $ \bmod{998244353} $ の定義求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $ \frac{P}{Q} $ で表した時、 $ Q {{}\not\equiv{}} 0 \pmod{998244353} $ となることも証明できます。 よって、 $ R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 $ を満たす整数 $ R $ が一意に定まります。 この $ R $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ $ \mathrm{case}_i $ は $ i $ 番目のテストケースであり、以下の形式で与えられる。 > $ N $ $ X $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについての答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、最終的に高橋君は確率 $ \frac{1}{8} $ で座標 $ -3 $ に、確率 $ \frac{3}{8} $ で座標 $ -1 $ に、確率 $ \frac{3}{8} $ で座標 $ 1 $ に、確率 $ \frac{1}{8} $ で座標 $ 3 $ にいます。 したがって $ |x'-X| $ の期待値は $ \frac{1}{8}\cdot|{-3}-2|+\frac{3}{8}\cdot|{-1}-2|+\frac{3}{8}\cdot|1-2|+\frac{1}{8}\cdot|3-2|=\frac{9}{4} $ です。 ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 1 \leq N \leq 2 \times 10^5 $ - $ |X| \leq 2 \times 10^5 $ - 入力はすべて整数