/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
整数 N,A が与えられます． (1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) であって，以下の条件を満たすものの個数を 998244353 で割った余りを求めてください．
- P_1=A
- 以下の操作を繰り返すことで，P の要素数を 2 にできる．
- 3 つの連続する要素 x,y,z を選ぶ． ただしこの時，y<\min(x,z) もしくは 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) になる．
Score : 1200 points
Problem Statement
Given are integers N and A. Find the number, modulo 998244353, of permutations P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N) that satisfy the following conditions.
- P_1=A.
- It is possible to repeat the following operation so that P has just two elements.
- Choose three consecutive elements x, y, and z. Here, y<\min(x,z) or y>\max(x,z) must hold. Then, erase y from P.
Solve T test cases in an input file.
Constraints
- 1 \leq T \leq 5 \times 10^5
- 3 \leq N \leq 10^6
- 1 \leq A \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is in the following format:
N A
Output
Print the answer for each test case.
Sample Input 1
8 3 1 3 2 3 3 4 1 4 2 4 3 4 4 200000 10000
Sample Output 1
1 2 1 3 5 5 3 621235018
When N=4,A=2, one permutation that satisfies the condition is P=(2,1,4,3). One way to make it have just two elements is as follows.
- Choose (x,y,z)=(2,1,4) to erase 1, resulting in P=(2,4,3).
- Choose (x,y,z)=(2,4,3) to erase 4, resulting in P=(2,3).