B4572 [合肥市初中组 2025 T4] 幸运排列

民间数据。

排列是长度为 $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$ 取模后的答案。

#### ****样例解释**** * 对于第一组数据，排列 $(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$ | $10^5$ | $10^6$ | $2$ | | $7 \sim 8$ | $10^5$ | $10^5$ | $10$ | | $9 \sim 10$ | $10^5$ | $10^6$ | $50$ |