{"problem":{"name":"Sequence Scores","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc114_c"},"statements":[{"statement_type":"Markdown","content":"For a sequence $A$ of length $N$ consisting of integers between $1$ and $M$ (inclusive), let us define $f(A)$ as follows:\n\n*   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:\n    *   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$.\n\nFind the sum, modulo $998244353$, of $f(A)$ over all $M^N$ sequences that can be $A$.\n\n## Constraints\n\n*   $1 \\leq N, M \\leq 5000$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc114_c","tags":[],"sample_group":[["2 3","15\n\nThe $3 ^ 2 = 9$ sequences and the value of $f$ for those are as follows:\n\n*   For $A = (1, 1)$, we can make $X$ equal it with one operation with $(l = 1, r = 2, v = 1)$, so $f(A) = 1$.\n*   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$.\n*   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$.\n*   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$.\n*   For $A = (2, 2)$, we can make $X$ equal it with one operation with $(l = 1, r = 2, v = 2)$, so $f(A) = 1$.\n*   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$.\n*   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$.\n*   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$.\n*   For $A = (3, 3)$, we can make $X$ equal it with one operation with $(l = 1, r = 2, v = 3)$, so $f(A) = 1$.\n\nThe sum of these values is $3 \\times 1 + 6 \\times 2 = 15$."],["3 2","15"],["34 56","649717324"]],"created_at":"2026-03-03 11:01:14"}}