当前没有测试数据。

F - 排列的分数

得分：$500$ 点

问题描述

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

• 有 $N$ 个人，编号为 $1,2,\dots,N$，并且还有一只 Snuke。最初，第 $i$ 个人（$1 \leq i \leq N$）拥有球 $i$。
  每当 Snuke 尖叫一次时，所有满足 $i \neq p_i$ 的第 $i$ 个人同时将自己的球传给第 $p_i$ 个人。
  如果，在至少尖叫一次之后，每个人都拥有自己的球，那么 Snuke 停止尖叫。
  分数即为 Snuke 尖叫的次数。保证分数是有限的。

有 $N!$ 种 $(1,2, \dots, N)$ 的排列 $P$。计算这些排列的分数的 $K$ 次方之和，模 $998244353$。

• 形式上，设 $S_N$ 为 $(1,2, \dots, N)$ 的排列的集合。计算下式： $\displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}$。

约束条件

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

输入

从标准输入读入输入数据，格式如下：

$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$。
  在此处，每个人都拥有自己的球，所以他停止尖叫。
  因此，分数为 $1$。

排列 $(2,1)$ 的分数计算如下。

• 最初，第 $1$ 个人拥有球 $1$，第 $2$ 个人拥有球 $2$。
  第一次 Snuke 尖叫后，第 $1$ 个人拥有球 $2$，第 $2$ 个人拥有球 $1$。
  第二次 Snuke 尖叫后，第 $1$ 个人拥有球 $1$，第 $2$ 个人拥有球 $2$。
  在此处，每个人都拥有自己的球，所以他停止尖叫。
  因此，分数为 $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