AT_abc463_g [ABC463G] Random Walk Distance

You are given a positive integer $ N $ and an integer $ X $ . Takahashi is at coordinate $ 0 $ on a number line. He will now perform the following move $ N $ times: - When at coordinate $ x $ , choose coordinate $ x-1 $ or coordinate $ x+1 $ with equal probability and move there. The choices of destination across the $ N $ moves are all independent. Let $ x' $ be the coordinate after all $ N $ moves. Find the expected value, modulo $ 998244353 $ , of $ |x'-X| $ . You are given $ T $ test cases; solve each of them. Definition of expected value modulo $ 998244353 $ It can be proved that the sought expected value is always a rational number. Moreover, under the constraints of this problem, it can be proved that when expressed as an irreducible fraction $ \frac{P}{Q} $ , we have $ Q {{}\not\equiv{}} 0 \pmod{998244353} $ . Therefore, there is a unique integer $ R $ satisfying $ R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 $ . Find this $ R $ .

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each $ \mathrm{case}_i $ is the $ i $ -th test case and is given in the following format: > $ N $ $ X $

Output $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 For the first test case, Takahashi ends up at coordinate $ -3 $ with probability $ \frac{1}{8} $ , at coordinate $ -1 $ with probability $ \frac{3}{8} $ , at coordinate $ 1 $ with probability $ \frac{3}{8} $ , and at coordinate $ 3 $ with probability $ \frac{1}{8} $ . Thus, the expected value of $ |x'-X| $ is $ \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 $ - All input values are integers.