P7292 「EZEC-5」「KrOI2021」Chasse Neige 加强版

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

**本题与原题的区别是 $r$ 的范围扩大了，应该能卡掉 $O(n\log^2n)$ 的分治 FFT 做法，如果有分治 FFT 能过请联系我。同时，如果你的做法是 $O(n\log n)$ 的话，请注意常数优化。** 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$。 ### 数据范围 对于 $100\%$ 的数据，$1\leq T\leq 2\times 10^5,3\leq n\leq r\leq 10^6,\max(1,\lfloor\frac{n-1}{2}\rfloor-10)\leq k\leq \lfloor\frac{n-1}{2}\rfloor$。