P7289 「EZEC-5」「KrOI2021」Chasse Neige

 『我喜欢雪。』 『之前虽然讨厌寒冷，现在却是最喜欢了。』 

Rikka 给了你 $T$ 组询问，每组询问给定两个正整数 $n,k$，你需要告诉 Rikka 有多少个长度为 $n$ 的排列 $\pi$ 满足如下条件： - $\pi_1\pi_{n}$ - 恰好存在 $k$ 个位置 $i(2\leq i\leq n-1)$ 满足 $\pi_{i-1}\pi_{i+1}$。 答案对 $998244353$ 取模。

无

无

### 样例解释 1 对于第一组询问，$n=3,k=1$，$(1,3,2)$ 和 $(2,3,1)$ 均满足条件，答案为 $2$。 对于第二组询问，满足条件的排列为： $$(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)$$ 共 $16$ 个，所以答案为 $16$。 ### 数据范围 | 子任务编号 | 分值 | $T\leq $ | $r\leq $ | 其他限制 | | :----------: | :----------: | :----------: | :----------: | :----------: | | Subtask 1 | $1$ | $1$ | $10$ | | | Subtask 2 | $5$ | $2\times 10^5$ | $10$ | | | Subtask 3 | $13$ | $1$ | $2\times 10^3$ | | | Subtask 4 | $13$ | $2\times 10^5$ | $2\times 10^3$ | | | Subtask 5 | $16$ | $2\times 10^5$ | $2\times 10^5$ | $k=\lfloor\frac{n-1}{2}\rfloor$ 且 $n$ 为奇数 | | 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$ | | 对于 $100\%$ 的数据，$1\leq T\leq 2\times 10^5,3\leq n\leq r\leq 2\times 10^5,\max(1,\lfloor\frac{n-1}{2}\rfloor-10)\leq k\leq \lfloor\frac{n-1}{2}\rfloor$。