Problem Description

In a mock contest, NaCly_Fish encountered the following problem:

Define the weight of a sequence $A$ of length $n$ as:

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$.

Input Format

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

Output Format

Output one line with one integer, representing the answer.

3 2

623902740

5 3

887328630

80 233

913763047

114514 19260817

850727003

Hint

[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