题目描述

$(1,2,\ \dots,\ N)$ を並び替えた長さ $N$ の順列 $P\ =\ (p_1,\ p_2,\ \dots,\ p_N)$ に対して、 $P$ のスコア $S(P)$ を次のように定めます。

• $N$ 人の人とすぬけ君がいて、$N$ 人の人には $1,2,\dots,N$ の番号がついています。はじめ、人 $i$ $(1\ \leq\ i\ \leq\ N)$ はボール $i$ を持っています。
  すぬけ君が叫ぶたびに、$i\ \neq\ p_i$ であるようなすべての人 $i$ は人 $p_i$ に持っているボールを同時に渡します。
  すぬけ君は、$1$ 回以上叫んだ後にすべての人 $i$ がボール $i$ を持っている状態になると叫ぶのをやめます。
  すぬけ君が叫ぶのをやめるまでに叫んだ回数が順列のスコアとなります。ここでスコアは有限の値を取ることが保証されます。

$P$ としてあり得るものは $N!$ 通りありますが、それらのスコアを $K$ 乗した値の総和を $998244353$ で割ったあまりを計算してください。

• 厳密に言い換えると、$(1,2,\ \dots,\ N)$ を並び替えた長さ $N$ の順列全体の集合を $S_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} $ を出力せよ。

题目大意

对于一个排列 $p$，我们记他的权值为 $S(p)$，要求你求出对于 $1$ 到 $n$ 的 $n!$ 种排列的权值的 $k$ 次方的和。 其中，$S(p)$被定义为如下过程的重复次数：

初始有一个数组 $a$ 满足 $\forall i \in [1,n]$，有 $a_i = i$。

$\forall i \in [1,n]$，$a'_{p_i} := a_i$。

$a = a'$

如果满足 $\forall i \in [1,n]$， $a_i = i$ 则结束此流程。

2 2

5

3 3

79

50 10000

77436607

提示

制約

• $2\ \leq\ N\ \leq\ 50$
• $1\ \leq\ K\ \leq\ 10^4$
• 入力はすべて整数である。

Sample Explanation 1

$N\ =\ 2$ のとき $P$ としてあり得る順列は $(1,2),(2,1)$ の $2$ つです。 順列 $(1,2)$ のスコアは次のように決まります。 - はじめ人 $1$ はボール $1$ を、人 $2$ はボール $2$ を持っています。 すぬけ君が $1$ 回目に叫んだ後に、人 $1$ はボール $1$ を、人 $2$ はボール $2$ を持っています。 このとき、すべての人が自身の番号と同じ番号が書かれたボールを持っているので、すぬけ君は叫ぶのをやめます。 よってスコアは $1$ となります。 順列 $(2,1)$ のスコアは次のように決まります。 - はじめ人 $1$ はボール $1$ を、人 $2$ はボール $2$ を持っています。 すぬけ君が $1$ 回目に叫んだ後に、人 $1$ はボール $2$ を、人 $2$ はボール $1$ を持っています。 すぬけ君が $2$ 回目に叫んだ後に、人 $1$ はボール $1$ を、人 $2$ はボール $2$ を持っています。 このとき、すべての人が自身の番号と同じ番号が書かれたボールを持っているので、すぬけ君は叫ぶのをやめます。 よってスコアは $2$ となります。 よって $1^2\ +\ 2^2\ =\ 5$ がこの問題の答えになります。

Sample Explanation 2

すべての順列とスコアの組を列挙すると以下のようになります。 - 順列 : $(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 $ を出力します。