/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
整数 N,K が与えられます．
1 以上 K 以下の整数からなる整数列 S に対し，スコア f(S) を次のように定義します．
-
S のすべての要素が等しくなるまで次の操作を繰り返す．この操作を行う回数が f(S) である．
- 操作前の S の長さを |S| とする．2 \leq i \leq |S| かつ S_{i-1} \ne S_i を満たすすべての i について，S の i 番目の要素を同時に削除する．削除せずに残った要素を元の順につなげて，新しい S とする．
1 以上 K 以下の整数からなる長さ N の整数列 S は K^N 通り存在します． そのすべてに対する f(S) の総和を 998244353 で割った余りを求めてください．
制約
- 2 \leq N \leq 100
- 2 \leq K < 998244353
- 入力はすべて整数である．
入力
入力は以下の形式で標準入力から与えられる．
N K
出力
答えを出力せよ．
入力例 1
3 2
出力例 1
8
(1,1,1),(2,2,2) のスコアは 0 で，(1,2,2),(2,1,1) のスコアは 2 です．その他 4 通りの整数列のスコアは 1 なので，総和は 8 です．
入力例 2
6 2
出力例 2
126
例えば，S=(1,2,2,2,1,2) は次のように変化するので，スコアは 3 です．
(1,2,2,2,1,2) \to (1,2,2) \to (1,2) \to (1)
入力例 3
2 2
出力例 3
2
入力例 4
10 3
出力例 4
145002
入力例 5
100 998244352
出力例 5
139448523
Score : 800 points
Problem Statement
You are given integers N and K.
For an integer sequence S consisting of integers between 1 and K, inclusive, define its score f(S) as follows.
-
Repeat the following operation until all elements of S are equal. The number of times this operation is performed is f(S).
- Let |S| be the length of S before the operation. For every i satisfying 2 \leq i \leq |S| and S_{i-1} \ne S_i, simultaneously delete the i-th element of S. Concatenate the remaining elements in their original order to form the new S.
There are K^N integer sequences S of length N consisting of integers between 1 and K, inclusive. Find the sum of f(S) over all of them, modulo 998244353.
Constraints
- 2 \leq N \leq 100
- 2 \leq K < 998244353
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
Output
Output the answer.
Sample Input 1
3 2
Sample Output 1
8
The scores of (1,1,1) and (2,2,2) are 0, and the scores of (1,2,2) and (2,1,1) are 2. The scores of the other four sequences are 1, so the sum is 8.
Sample Input 2
6 2
Sample Output 2
126
For example, S=(1,2,2,2,1,2) changes as follows, so its score is 3.
(1,2,2,2,1,2) \to (1,2,2) \to (1,2) \to (1)
Sample Input 3
2 2
Sample Output 3
2
Sample Input 4
10 3
Sample Output 4
145002
Sample Input 5
100 998244352
Sample Output 5
139448523