题目背景

民间数据。

题目描述

排列是长度为 $n$ 的从 $1$ 到 $n$ 的整数序列，其中每个数字都恰好出现一次。例如，$(1)$、$(4, 3, 5, 1, 2)$、$(3, 2, 1)$ 是排列，而 $(1, 1)$、$(4, 3, 1)$、$(2, 3, 4)$ 不是排列。

小 C 最近在研究排列，他认为每个排列的幸运程度不同。具体来说，一个排列的幸运值定义为其前缀最小值个数的 $d$ 次方。这里对于长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$，满足 $\min_{i=1}^k p_i = p_k$ 的整数 $k$（$1 \le k \le n$）的个数称为 $p$ 的前缀最小值个数。

现在小 C 想知道全体长度为 $n$ 的排列的幸运值之和是多少，由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。

输入格式

本题包含多组测试数据。

第一行包含一个正整数 $T$，表示数据组数。

接下来 $T$ 行，每行描述一组数据，包含一个正整数 $n$ 和一个非负整数 $d$，中间用一个空格隔开。

输出格式

输出共 $T$ 行，每行一个整数，依次表示每组数据对 $998244353$ 取模后的答案。

2
3 2
5 0

23
120

2
5 4
8 47

6844
219698089

提示

样例解释

• 对于第一组数据，排列 $(1,2,3)$、$(1,3,2)$ 的前缀最小值个数为 $1$，幸运值为 $1^2=1$；排列 $(2,1,3)$、$(2,3,1)$、$(3,1,2)$ 的前缀最小值个数为 $2$，幸运值为 $2^2=4$；排列 $(3,2,1)$ 的前缀最小值个数为 $3$，幸运值为 $3^2=9$。因此幸运值之和为 $2 \times 1 + 3 \times 4 + 1 \times 9 = 23$。
• 对于第二组数据，因为 $d=0$，每个排列的幸运值都是 $1$。而长度为 $5$ 的排列共有 $5! = 120$ 个，因此幸运值之和为 $120$。

其它样例说明

• 样例 $3$：见选手附加文件目录下的 luck/luck3.in 与 luck/luck3.ans。该样例满足测试点 $5 \sim 6$ 的约束条件。
• 样例 $4$：见选手附加文件目录下的 luck/luck4.in 与 luck/luck4.ans。该样例满足测试点 $7 \sim 8$ 的约束条件。

数据范围

对于所有数据，保证 $1 \le T \le 10^5, 1 \le n \le 10^6, 0 \le d \le 50$。 保证所有的输入数值均为整数。

各测试点的附加限制如下表所示：

测试点编号	$T \le$	$n \le$	$d \le$
$1 \sim 2$	$5$	$8$	$50$
$3 \sim 4$	$10^5$	$10^6$	$1$
$5 \sim 6$			$2$
$7 \sim 8$		$10^5$	$10$
$9 \sim 10$		$10^6$	$50$