P7289 "EZEC-5" "KrOI2021" Chasse Neige

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

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

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 $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 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$ | $1$ | $10$ | | | Subtask 2 | $5$ | $2\times 10^5$ | $10$ | | | Subtask 3 | $13$ | $1$ | $2\times 10^5$ | | | Subtask 4 | $13$ | $2\times 10^5$ | $2\times 10^5$ | | | Subtask 5 | $16$ | $2\times 10^5$ | $2\times 10^5$ | $k=\lfloor\frac{n-1}{2}\rfloor$ and $n$ is odd | | Subtask 6 | $16$ | $2\times 10^5$ | $2\times 10^5$ | $k=\lfloor\frac{n-1}{2}\rfloor-1$ | | Subtask 7 | $36$ | $2\times 10^5$ | $2\times 10^5$ | | 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