Background

"I like snow."

"Although I used to hate the cold, now it is my favorite."

Problem Description

Rikka gives you $T$ queries. In each query, two positive integers $n, k$ are given. You need to tell Rikka how many permutations $\pi$ of length $n$ satisfy the following conditions:

• $\pi_1 < \pi_2$.

• $\pi_{n-1} > \pi_n$.

• There exist exactly $k$ positions $i \ (2 \leq i \leq n - 1)$ such that $\pi_{i-1} < \pi_i$ and $\pi_i > \pi_{i+1}$.

Output the answer modulo $998244353$.

Input Format

The first line contains two integers $T, r$, representing the number of queries and the upper bound of the range of $n$.

The next $T$ lines each contain two integers $n, k$, with the meaning as described above.

Output Format

Output $T$ lines. Each line contains one positive integer, the answer modulo $998244353$.

2 10
3 1
5 2

2
16

Hint

Sample Explanation 1

For the first query, $n = 3, k = 1$. Both $(1,3,2)$ and $(2,3,1)$ satisfy the conditions, so the answer is $2$.

For the second query, the permutations that satisfy the conditions are:

$$(1,3,2,5,4),(1,4,2,5,3),(1,4,3,5,2),(1,5,2,4,3),(1,5,3,4,2)\\(2,3,1,5,4),(2,4,1,5,3),(2,4,3,5,1),(2,5,1,4,3),(2,5,3,4,1)\\(3,4,1,5,2),(3,4,2,5,1),(3,5,1,4,2),(3,5,2,4,1),(4,5,1,3,2),(4,5,2,3,1)$$

There are $16$ in total, so the answer is $16$.

Constraints

Subtask ID	Points	$T \leq$	$r \leq$	Other Constraints
Subtask 1	$1$		$10$
Subtask 2	$5$	$2\times 10^5$
Subtask 3	$13$	$1$	$2\times 10^5$
Subtask 4		$2\times 10^5$
Subtask 5	$16$			$k=\lfloor\frac{n-1}{2}\rfloor$ and $n$ is odd
Subtask 6				$k=\lfloor\frac{n-1}{2}\rfloor-1$
Subtask 7	$36$

For $100\%$ of the testdata, $1 \leq T \leq 2\times 10^5$, $3 \leq n \leq r \leq 2\times 10^5$, and $\max(1,\lfloor\frac{n-1}{2}\rfloor-10) \leq k \leq \lfloor\frac{n-1}{2}\rfloor$.

Translated by ChatGPT 5