P7292 "EZEC-5" "KrOI2021" Chasse Neige Enhanced Version

 "I like snow." "Even though I used to hate the cold, now it is my favorite." 

**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$.

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 $T$ lines. Each line contains one positive integer, the answer modulo $998244353$.

### 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