P7423 "PMOI-2" Simple Construction Problem

In a mock contest, NaCly\_Fish encountered the following problem: **** Define the weight of a sequence $A$ of length $n$ as: $$\sum_{l=1}^n\sum_{r=l}^n f_A(l,r)$$ where $f_A(l,r)$ is: in the subarray $[l,r]$ of $A$, take the product of the occurrence counts of all elements that have appeared in this subarray, and then multiply it by the product of all elements in the subarray. You are required to construct a sequence of length $n$, where each element is an integer in $[1,m]$, to maximize its weight. **** She could not do it, so she uniformly randomly picked $n$ integers from $[1,m]$ to form a sequence, and then output its weight. Of course, her program got zero points. However, she wants to know the expected weight of the generated sequence. To avoid precision issues, you need to output the answer modulo $998244353$.

One line with two positive integers $n, m$.

Output one line with one integer, representing the answer.

[Explanation of Sample 1] Clearly there are $8$ possible sequences: $[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]$. Their weights are $10,12,12,23,12,17,23,46$, respectively, so the expectation is $\frac{155}{8}$. [Explanation of Sample 2] The expectation is $\frac{76842}{243}$. [Constraints] **This problem uses bundled testdata**. - Subtask 1 (5 pts): $1\le n,m \le 8$. - Subtask 2 (7 pts): $1\le n,m \le 100$. - Subtask 3 (11 pts): $1 \le n,m \le 400$. - Subtask 4 (13 pts): $1\le n,m \le 5000$. - Subtask 5 (25 pts): $1\le n \le 5000$. - Subtask 6 (39 pts): no additional constraints. For $100\%$ of the testdata, $1\le n \le 2 \times 10^5$, $1\le m \le 10^8$. Translated by ChatGPT 5