Crying 与排列

Crying 与排列

题号：NC264866
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Crying 正在数排列。

Crying 给了你 $T$ 组询问，每组询问给定两个正整数 $n,k$ ，你需要告诉 Crying 有多少个长度为 $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$ 取模。

另外，Crying 会在所有询问之前告诉你所有询问中 $n$ 的最大值和 $n-2k$ 的最大值。

输入描述:

第一行三个整数 $T,r,m$ ，表示询问次数、 $\max n$ 和 $\max (n-2k)$ 。

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

对于所有数据， $1\le T\le 2\times 10^5$ ， $3\le n\le 5 \times 10^5$ ， $1 \le k \le \left\lfloor\frac{n-1}2\right\rfloor$ ， $r = \max n$ ， $m = \max(n-2k)$ ， $r+m \le 5 \times 10^5$ ， $\sum(n-2k) \le 5 \times 10^5$ 。

输出描述:

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

示例1

输入

复制

2 5 1
3 1
5 2

输出

复制

2
16

说明

对于第一组询问，满足条件的排列为 $(1,3,2)$ 和 $(2,3,1)$ ，共 $2$ 个。

对于第二组询问，满足条件的排列为

$\begin{array}{llll}<br />(1,3,2,5,4), &(1,4,2,5,3), &(1,4,3,5,2), &(1,5,2,4,3), \\<br />(1,5,3,4,2), &(2,3,1,5,4), &(2,4,1,5,3), &(2,4,3,5,1), \\<br />(2,5,1,4,3), &(2,5,3,4,1), &(3,4,1,5,2), &(3,4,2,5,1), \\<br />(3,5,1,4,2), &(3,5,2,4,1), &(4,5,1,3,2), &(4,5,2,3,1)<br />\end{array}$

共 $16$ 个。

示例2

输入

复制

输出

复制

126
254
510