题目背景

『我喜欢雪。』

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

题目描述

本题与原题的区别是 $r$ 的范围扩大了，应该能卡掉 $O(n\log^2n)$ 的分治 FFT 做法，如果有分治 FFT 能过请联系我。同时，如果你的做法是 $O(n\log n)$ 的话，请注意常数优化。

Rikka 给了你 $T$ 组询问，每组询问给定两个正整数 $n,k$，你需要告诉 Rikka 有多少个长度为 $n$ 的排列 $\pi$ 满足如下条件：

• $\pi_1<\pi_2$

• $\pi_{n-1}>\pi_{n}$

• 恰好存在 $k$ 个位置 $i(2\leq i\leq n-1)$ 满足 $\pi_{i-1}<\pi_{i}$ 且 $\pi_{i}>\pi_{i+1}$。

答案对 $998244353$ 取模。

输入格式

第一行两个整数 $T,r$，表示询问次数以及 $n$ 的值域。

接下来 $T$ 行，每行两个整数 $n,k$，意义如题意所示。

输出格式

$T$ 行，每行一个正整数，表示答案对 $998244353$ 取模的值。

2 10
3 1
5 2

2
16

提示

样例解释 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$。