Contest Duration: - (local time) (120 minutes) Back to Home
C - Sequence Scores /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1 以上 M 以下の整数から成る長さ N の数列 A に対して， f(A) を以下のように定義します．

• 長さ N の数列 X があり，初め全ての要素は 0 である．f(A) を，次の操作を繰り返して XA に等しくするための最小の操作回数とする．
• 1 \leq l \leq r \leq N1 \leq v \leq M を指定する．l \leq i \leq r に対して X_i\max(X_i, v) で置き換える．

A として考えられる数列は M^N 通りあります．これら全ての数列に対する f(A) の和を 998244353 で割った余りを求めてください．

### 制約

• 1 \leq N, M \leq 5000
• 入力は全て整数

### 入力

N M


### 入力例 1

2 3


### 出力例 1

15


3 ^ 2 = 9 通りの数列と，それに対する f の値は以下の通りです．

• A = (1, 1) のとき，(l = 1, r = 2, v = 1) として 1 回の操作で可能なので，f(A) = 1 です．
• A = (1, 2) のとき，(l = 1, r = 2, v = 1) , (l = 2, r = 2, v = 2) として 2 回の操作で可能なので，f(A) = 2 です．
• A = (1, 3) のとき，(l = 1, r = 2, v = 1) , (l = 2, r = 2, v = 3) として 2 回の操作で可能なので，f(A) = 2 です．
• A = (2, 1) のとき，(l = 1, r = 2, v = 1) , (l = 1, r = 1, v = 2) として 2 回の操作で可能なので，f(A) = 2 です．
• A = (2, 2) のとき，(l = 1, r = 2, v = 2) として 1 回の操作で可能なので，f(A) = 1 です．
• A = (2, 3) のとき，(l = 1, r = 2, v = 2) , (l = 2, r = 2, v = 3) として 2 回の操作で可能なので，f(A) = 2 です．
• A = (3, 1) のとき，(l = 1, r = 2, v = 1) , (l = 1, r = 1, v = 3) として 2 回の操作で可能なので，f(A) = 2 です．
• A = (3, 2) のとき，(l = 1, r = 2, v = 2) , (l = 1, r = 1, v = 3) として 2 回の操作で可能なので，f(A) = 2 です．
• A = (3, 3) のとき，(l = 1, r = 2, v = 3) として 1 回の操作で可能なので，f(A) = 1 です．

これらの和は 3 \times 1 + 6 \times 2 = 15 です．

### 入力例 2

3 2


### 出力例 2

15


### 入力例 3

34 56


### 出力例 3

649717324


Score : 600 points

### Problem Statement

For a sequence A of length N consisting of integers between 1 and M (inclusive), let us define f(A) as follows:

• We have a sequence X of length N, where every element is initially 0. f(A) is the minimum number of operations required to make X equal A by repeating the following operation:
• Specify 1 \leq l \leq r \leq N and 1 \leq v \leq M, then replace X_i with \max(X_i, v) for each l \leq i \leq r.

Find the sum, modulo 998244353, of f(A) over all M^N sequences that can be A.

### Constraints

• 1 \leq N, M \leq 5000
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N M


### Output

Print the sum of f(A) over all sequences A, modulo 998244353.

### Sample Input 1

2 3


### Sample Output 1

15


The 3 ^ 2 = 9 sequences and the value of f for those are as follows:

• For A = (1, 1), we can make X equal it with one operation with (l = 1, r = 2, v = 1), so f(A) = 1.
• For A = (1, 2), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 2, r = 2, v = 2), so f(A) = 2.
• For A = (1, 3), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 2, r = 2, v = 3), so f(A) = 2.
• For A = (2, 1), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 1, r = 1, v = 2), so f(A) = 2.
• For A = (2, 2), we can make X equal it with one operation with (l = 1, r = 2, v = 2), so f(A) = 1.
• For A = (2, 3), we can make X equal it with two operations with (l = 1, r = 2, v = 2) , (l = 2, r = 2, v = 3), so f(A) = 2.
• For A = (3, 1), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 1, r = 1, v = 3) so f(A) = 2.
• For A = (3, 2), we can make X equal it with two operations with (l = 1, r = 2, v = 2) and (l = 1, r = 1, v = 3), so f(A) = 2.
• For A = (3, 3), we can make X equal it with one operation with (l = 1, r = 2, v = 3), so f(A) = 1.

The sum of these values is 3 \times 1 + 6 \times 2 = 15.

### Sample Input 2

3 2


### Sample Output 2

15


### Sample Input 3

34 56


### Sample Output 3

649717324