P15738 [JAG 2024 Summer Camp #2] Just Believe in Binary Search

正在遗迹中探索宝藏的 Alice 来到了一条走廊，走廊上并排着 $N$ 个房间的入口。经过调查，她发现房间被唯一地编号为 $1$ 到 $N$，但每个房间的具体编号直到进入后才能知晓。她得知宝藏藏在编号为 $K$ 的房间中。 考虑到剩余的体力，Alice 很难检查所有房间。然而，Alice 有一个应对此困境的秘密策略：**二分查找**。Alice 之前曾成功地将二分查找应用于各种挑战。她决定用尽最后的力量，使用二分查找来寻找房间 $K$。 具体来说，她遵循以下步骤： - 初始化变量 $l$ 和 $r$，令 $l = 0$，$r = N + 1$。 - 重复执行步骤 1 到 3： 1. 如果 $l + 1 = r$，则停止操作，因为她未能找到房间 $K$。 2. 令 $m = \left\lfloor \frac{l + r}{2} \right\rfloor$。进入从左数第 $m$ 个房间，检查其编号，记该编号为 $x$。 3. 如果 $x = K$，则停止操作，因为她找到了房间 $K$。如果 $x < K$，则将 $l$ 更新为 $m$。如果 $x > K$，则将 $r$ 更新为 $m$。 房间与编号之间共有 $N!$ 种可能的映射关系。你需要计算，在这些映射中，有多少种映射能使得 Alice 通过上述过程成功找到房间 $K$，答案对 $998,244,353$ 取模。 给定 $T$ 个测试用例，计算每个用例的答案。

输入以如下格式给出： $$ \begin{aligned} &T \\ &\text{case}_1 \\ &\text{case}_2 \\ &\vdots \\ &\text{case}_T \end{aligned} $$ 其中，$\text{case}_i$ 表示第 $i$ 个测试用例。 每个测试用例以如下格式给出： $$ N \ K $$ - $1 \leq T \leq 100,000$ - $3 \leq N \leq 10^6$ - $1 \leq K \leq N$ - 所有输入值均为整数。

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

翻译由 DeepSeek V3.2 完成