P15713 [JAG 2023 Summer Camp #2] Empty Quartz

有 $N$ 个水晶排成一行。然而，其中一些可能是幻影。 Jun 对于每一对 $l, r (1 \leq l \leq r \leq N)$，统计了从第 $l$ 个到第 $r$ 个（闭区间）真实水晶的数量，并记录了其奇偶性。 他的 $\frac{N(N+1)}{2}$ 条记录显示，有 $K$ 个区间包含了奇数个真实水晶。有多少种可能的水晶排列方式？请输出答案除以 $998244353$ 的余数。 注意，如果存在某个 $i$，使得从左数第 $i$ 个水晶在一种排列中是真实的，而在另一种中是幻影，则这两种排列被认为是不同的。 你被给出了 $T$ 个上述问题。请回答每个问题。

$$ \begin{aligned} &T \\ &N_1 \ K_1 \\ &\vdots \\ &N_T \ K_T \end{aligned} $$ 输入满足以下约束： - 所有输入均为整数。 - $1 \leq T \leq 10^5$ - $1 \leq N_i \leq 10^5$ - $0 \leq K_i \leq \frac{N_i(N_i+1)}{2}$

输出 $T$ 行。在第 $i$ 行，回答当 $N = N_i, K = K_i$ 时的问题。请在每行末尾添加换行符。

如果我们用 $1$ 表示真实水晶，用 $0$ 表示幻影，那么以下三种排列满足样例输入 1 的条件： - $0, 1, 0$ - $1, 0, 1$ - $1, 1, 1$ 翻译由 DeepSeek V3.2 完成