排列的分数

题目描述

对于 $(1,2,\dots,N)$ 的一个排列 $P = (p_1, p_2, \dots, p_N)$,如下定义 $P$ 的分数 $S(P)$。

有 $N$ 个人,编号为 $1, 2, \dots, N$。此外,Snuke 也在场。初始时,第 $i$ 个人($1 \le i \le N$)拿着球 $i$。

每次 Snuke 大喊时,所有满足 $i \neq p_i$ 的第 $i$ 个人会同时把自己的球交给第 $p_i$ 个人。

如果在大喊至少一次之后,每个人 $i$ 都拿着自己的球 $i$,Snuke 就停止大喊。

分数是 Snuke 在停止前大喊的次数。这里保证分数一定是有限值。

$(1,2,\dots,N)$ 共有 $N!$ 个排列 $P$。求所有排列的分数 $S(P)$ 的 $K$ 次方之和,对 $998244353$ 取模。

形式化地说,设 $S_N$ 为 $(1,2,\dots,N)$ 的所有排列的集合,计算下式:

$\displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}$

输入格式

输入按以下格式从标准输入给出:

$N$ $K$

输出格式

输出 $\displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}$。

样例

2 2

5

当 $N = 2$ 时,可能的排列 $P$ 有 $(1,2)$ 和 $(2,1)$ 两个。

排列 $(1,2)$ 的分数求解如下。

初始时,第 $1$ 个人拿着球 $1$,第 $2$ 个人拿着球 $2$。

在 Snuke 第一次大喊之后,第 $1$ 个人拿着球 $1$,第 $2$ 个人拿着球 $2$。

此时每个人都拿着自己的球 $i$,所以他停止大喊。

因此,分数是 $1$。

排列 $(2,1)$ 的分数求解如下。

初始时,第 $1$ 个人拿着球 $1$,第 $2$ 个人拿着球 $2$。

在 Snuke 第一次大喊之后,第 $1$ 个人拿着球 $2$,第 $2$ 个人拿着球 $1$。

在 Snuke 第二次大喊之后,第 $1$ 个人拿着球 $1$,第 $2$ 个人拿着球 $2$。

此时每个人都拿着自己的球 $i$,所以他停止大喊。

因此,分数是 $2$。

因此,本题的答案是 $1^2 + 2^2 = 5$。

3 3

79

所有排列及其分数如下。

$(1,2,3)$:分数为 $1$。

$(1,3,2)$:分数为 $2$。

$(2,1,3)$:分数为 $2$。

$(2,3,1)$:分数为 $3$。

$(3,1,2)$:分数为 $3$。

$(3,2,1)$:分数为 $2$。

因此,应输出 $1^3 + 2^3 + 2^3 + 3^3 + 3^3 + 2^3 = 79$。

50 10000

77436607

数据范围

• $2 \le N \le 50$
• $1 \le K \le 10^4$
• 输入中的所有值均为整数。