C - Sequence Scores Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

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

出力

全ての数列に対する f(A) の和を 998244353 で割った余りを出力せよ.


入力例 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