资格赛

题目描述

给定整数 $N,K$，保证 $K \le \frac{N}{2}$。

对于 $(1,2,\ldots,N)$ 的两个排列 $P=(P_1,P_2,\ldots,P_N)$、$Q=(Q_1,Q_2,\ldots,Q_N)$，如下定义 $f(P,Q)$：

有 $N$ 个人，编号为 $1$ 到 $N$，参加了比赛 A 和比赛 B。第 $i$ 个人（$1 \le i \le N$）在比赛 A 中排名第 $P_i$，在比赛 B 中排名第 $Q_i$。

考虑用以下两种选择方法选出这 $N$ 个人中的 $2K$ 个人：

• 方法 ①：先选出比赛 A 中排名最好的 $K$ 个人；再在剩下的 $N-K$ 个人中，选出比赛 B 中排名最好的 $K$ 个人。
• 方法 ②：先选出比赛 B 中排名最好的 $K$ 个人；再在剩下的 $N-K$ 个人中，选出比赛 A 中排名最好的 $K$ 个人。

设 $f(P,Q)$ 为「被方法 ① 选中、但没有被方法 ② 选中」的人数。

共有 $N!^2$ 对排列 $(P,Q)$。请求出所有 $f(P,Q)$ 之和对 $998244353$ 取模的结果。

本题有 $T$ 组测试数据，请分别求解。

输入格式

输入第一行为一个整数 $T$。

接下来 $T$ 行，第 $i$ 行为两个整数 $N,K$。

输出格式

输出 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据的答案。

4
3 1
6 3
9 2
483 101

6
0
982675409
845255482

样例 1 解释

考虑第 $1$ 组测试数据。

例如当 $P=(2,1,3)$、$Q=(3,1,2)$ 时，方法 ① 选中的人为第 $2,3$ 个人，方法 ② 选中的人为第 $1,2$ 个人，因此 $f(P,Q)=1$。

满足 $f(P,Q)=1$ 的排列对有 $6$ 对，其余 $30$ 对满足 $f(P,Q)=0$，所以答案为 $6 \times 1 + 30 \times 0 = 6$。

数据范围

对于所有测试数据，保证：

• $1 \le T \le 2 \times 10^5$；
• $2 \le N \le 10^6$；
• $1 \le K \le \frac{N}{2}$；
• 所有测试数据的 $N$ 之和不超过 $10^6$；
• 所有输入值均为整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。