AT_abc463_g.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$.

给定一个正整数 $N$ 和一个整数 $X$。

高桥位于数轴上的坐标 $0$ 处。他将执行以下操作共 $N$ 次：

• 当前位于坐标 $x$ 时，以相等的概率选择坐标 $x-1$ 或 $x+1$，并移动到该位置。

这 $N$ 次移动中每次的选择相互独立。设 $N$ 次移动后最终坐标为 $x'$。求 $|x'-X|$ 的期望值对 $998244353$ 取模的结果。

你将得到 $T$ 组测试用例，请分别求解每组。

期望值对 $998244353$ 取模的定义

可以证明：所求期望值恒为有理数。此外，在本题约束下，可进一步证明：若将该期望值表示为既约分数 $\frac{P}{Q}$，则必有 $Q {{}\not\equiv{}} 0 \pmod{998244353}$。因此，存在唯一整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出该 $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$

输入从标准输入中按以下格式给出：

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

每个 $\mathrm{case}_i$ 表示第 $i$ 个测试用例，其格式如下：

$N$ $X$

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

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

Sample 1 Explanation:
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.

样例 1 解释：
对于第一个测试用例，高桥最终位于坐标 $-3$ 的概率为 $\frac{1}{8}$，位于坐标 $-1$ 的概率为 $\frac{3}{8}$，位于坐标 $1$ 的概率为 $\frac{3}{8}$，位于坐标 $3$ 的概率为 $\frac{1}{8}$。因此，$|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}.$$

限制条件

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $|X| \leq 2 \times 10^5$
• 所有输入值均为整数。