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

Alice, who was exploring ruins in search of treasure, arrived at a corridor where the entrances to $N$ rooms were lined up in a row. Upon investigation, she found that the rooms were numbered uniquely from $1$ to $N$, but the exact number of each room was unknown until she entered. She discovered that the treasure was hidden in room $K$. Given her remaining stamina, it was difficult for Alice to check all the rooms. However, Alice had a secret strategy to overcome this situation: binary search. Alice had successfully applied binary search to various challenges before. With her last ounce of strength, she decided to use binary search to find room $K$. Specifically, she followed these steps: - Initialize variables $l$ and $r$ with $l = 0$ and $r = N + 1$. - Repeat steps 1 to 3 as follows: 1. If $l + 1 = r$, stop the operation as she has not found room $K$. 2. Set $m = \left\lfloor \frac{l + r}{2} \right\rfloor$. Enter the room positioned $m$-th from the left, check its number, and let this number be $x$. 3. If $x = K$, stop the operation as she has found room $K$. If $x < K$, update $l$ to $m$. If $x > K$, update $r$ to $m$. There are $N!$ possible mappings between rooms and numbers. You need to determine the number of mappings for which Alice can successfully find room $K$ using the above procedure, modulo $998,244,353$. Given $T$ test cases, compute the answer for each.

The input is given in the following format: $$ \begin{aligned} &T \\ &\text{case}_1 \\ &\text{case}_2 \\ &\vdots \\ &\text{case}_T \end{aligned} $$ Here, $\text{case}_i$ denotes the $i$-th test case. Each test case is given in the following format: $$ N \ K $$ - $1 \leq T \leq 100,000$ - $3 \leq N \leq 10^6$ - $1 \leq K \leq N$ - All input values are integers.

Output $T$ lines. On the $i$-th line, output the answer for the $i$-th test case.