[R41F]幸运 - 代码源竞赛平台

时空限制

1.5S/512M

题目描述

排列是指一个长度为 $n$ 的序列，其中从 $1$ 到 $n$ 的每个整数恰好出现一次。

apiadu 最近在研究排列，他认为每个排列的“幸运程度”是不同的。具体来说，对于一个长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$，定义其 前缀最小值数量 $K$ 为满足以下条件的下标 $k$ ($1 \le k \le n$) 的个数：

$$\min(p_1, p_2, \dots, p_k) = p_k$$

换句话说，如果 $p_k$ 是序列 $p_1, \dots, p_k$ 中的最小值，那么它就贡献 $1$ 个计数。

接着，定义该排列的 幸运值 为 $K^d$，其中 $d$ 是一个给定的非负整数。

现在 apiadu 想知道：对于所有长度为 $n$ 的排列，它们的幸运值之和是多少？

由于答案可能非常大，请输出答案对 $998244353$ 取模后的结果。

格式

输入格式

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

接下来 $T$ 行，每行包含两个整数 $n$ 和 $d$，表示一组询问。

输出格式

输出 $T$ 行，每行一个整数，表示该组询问的答案对 $998244353$ 取模后的结果。

样例

样例输入 #1

2
3 2
5 0

样例输出 #1

23
120

样例解释 #1

对于 $n=3, d=2$：

• 排列 1 2 3：前缀最小值为 1，个数 $K=1$，幸运值 $1^2=1$。
• 排列 1 3 2：前缀最小值为 1，个数 $K=1$，幸运值 $1^2=1$。
• 排列 2 1 3：前缀最小值为 2, 1，个数 $K=2$，幸运值 $2^2=4$。
• 排列 2 3 1：前缀最小值为 2, 1，个数 $K=2$，幸运值 $2^2=4$。
• 排列 3 1 2：前缀最小值为 3, 1，个数 $K=2$，幸运值 $2^2=4$。
• 排列 3 2 1：前缀最小值为 3, 2, 1，个数 $K=3$，幸运值 $3^2=9$。 总和为 $1+1+4+4+4+9 = 23$。

对于 $n=5, d=0$： 任意排列的幸运值为 $K^0 = 1$。 长度为 $5$ 的排列共有 $5! = 120$ 个，故总和为 $120$。

样例输入 #2

2
5 4
8 20

样例输出 #2

6844
708009807

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	$n \le$	$d \le$	$T \le$	分值	依赖子任务
$1$	$8$	$5$	$10$	$20$	无
$2$	$100$	$10$	$100$	$30$	$1$
$3$	$1 \le n \le 10^5$	$20$	$4 \times 10^4$	$50$	$1, 2$

对于 $100\%$ 的数据，保证 $1 \le T \le 4 \times 10^4$，$1 \le n \le 10^5$，$0 \le d \le 20$。