分数: 1200 点
问题陈述
给定的是整数 N 和 A。 求模数 998244353,排列 P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N) 满足以下条件。
- P_1=A.
- 可以重复以下操作,以便 P 只有两个元素。
- 选择三个 连续 元素 x, y,和 z。 在这里, y<\min(x,z) or y>\max(x,z) 必须保留。 然后,擦除 y 来自 P.
解决 输入文件中的 T 测试用例。
约束
- 1 \leq T \leq 5 \times 10^5
- 3 \leq N \leq 10^6
- 1 \leq A \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例的格式如下:
N A
输出
打印每个测试用例的答案。
样本输入 1
8 3 1 3 2 3 3 4 1 4 2 4 3 4 4 200000 10000
示例输出 1
1 2 1 3 5 5 3 621235018
当 N=4,A=2,满足条件的一种排列是 P=(2,1,4,3)。 使其只有两个元素的一种方法如下。
- 选择 (x,y,z)=(2,1,4) 擦除 1,导致 P=(2,4,3).
- 选择 (x,y,z)=(2,4,3) 擦除 4,导致 P=(2,3).