Description

The difference from the original problem is that the range of $r$ is enlarged. This should be able to block the $O(n\log^2 n)$ divide-and-conquer FFT solution. If there is a divide-and-conquer FFT solution that can pass, please contact me. Also, if your solution is $O(n\log n)$, please pay attention to constant-factor optimization.

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 \le i \le n - 1)$ such that $\pi_{i-1} < \pi_i$ and $\pi_i > \pi_{i+1}$.

Take the answer modulo $998244353$.

Input Format

The first line contains two integers $T, r$, representing the number of queries and the range of possible values 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 valid permutations 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

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

Translated by ChatGPT 5