/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
(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}
を計算してください。
制約
- 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} を出力せよ。
入力例 1
2 2
出力例 1
5
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 がこの問題の答えになります。
入力例 2
3 3
出力例 2
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 を出力します。
入力例 3
50 10000
出力例 3
77436607
Score : 500 points
Problem Statement
For a permutation P = (p_1, p_2, \dots, p_N) of (1,2, \dots, N), let us define the score S(P) of P as follows.
- There are N people, numbered 1,2,\dots,N. Additionally, Snuke is there. Initially, Person i (1 \leq i \leq N) has Ball i.
Each time Snuke screams, every Person i such that i \neq p_i gives their ball to Person p_i simultaneously.
If, after screaming at least once, every Person i has Ball i, Snuke stops screaming.
The score is the number of times Snuke screams until he stops. Here, it is guaranteed that the score will be a finite value.
There are N! permutations P of (1,2, \dots, N). Find the sum, modulo 998244353, of the scores of those permutations, each raised to the K-th power.
- Formally, let S_N be the set of the permutations of (1,2, \dots, N). Compute the following: \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.
Constraints
- 2 \leq N \leq 50
- 1 \leq K \leq 10^4
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.
Sample Input 1
2 2
Sample Output 1
5
When N = 2, there are two possible permutations P: (1,2),(2,1).
The score of the permutation (1,2) is found as follows.
- Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
After Snuke's first scream, Person 1 has Ball 1, and Person 2 has Ball 2.
Here, every Person i has Ball i, so he stops screaming.
Thus, the score is 1.
The score of the permutation (2,1) is found as follows.
- Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
After Snuke's first scream, Person 1 has Ball 2, and Person 2 has Ball 1.
After Snuke's second scream, Person 1 has Ball 1, and Person 2 has Ball 2.
Here, every Person i has Ball i, so he stops screaming.
Thus, the score is 2.
Therefore, the answer in this case is 1^2 + 2^2 = 5.
Sample Input 2
3 3
Sample Output 2
79
All permutations and their scores are listed below.
- (1,2,3): The score is 1.
- (1,3,2): The score is 2.
- (2,1,3): The score is 2.
- (2,3,1): The score is 3.
- (3,1,2): The score is 3.
- (3,2,1): The score is 2.
Thus, we should print 1^3 + 2^3 + 2^3 + 3^3 + 3^3 + 2^3 = 79.
Sample Input 3
50 10000
Sample Output 3
77436607