Expected Weighted Sum on Random Sequences

Consider a sequence \(A\) of length \(n\) where each element is an integer chosen uniformly at random from \([1, M]\). For any subarray defined by indices \(l, r\) (with \(1 \le l \le r \le n\)), define its value as

[ f_A(l,r) = \Bigl( \prod_{x,\in,{A_l, A_{l+1}, \ldots, A_r}} \mathrm{cnt}(x) \Bigr) \cdot \Bigl( \prod_{i=l}^{r} A_i \Bigr), ]

where \(\mathrm{cnt}(x)\) is the number of occurrences of \(x\) in the subarray \(A[l, r]\) (each distinct element \(x\) contributes its frequency exactly once to the product). The overall weight of the sequence \(A\) is defined as the sum of \(f_A(l,r)\) over all subarrays:

[ W(A) = \sum_{l=1}^{n} \sum_{r=l}^{n} f_A(l,r). ]

Since it is difficult to construct a sequence that maximizes \(W(A)\), one may instead consider a sequence generated by choosing each \(A_i\) uniformly at random from \([1, M]\) and then output its weight \(W(A)\). Your task is to compute the expected value of \(W(A)\) modulo \(998244353\).

Note: The answer is guaranteed to be a rational number and should be given modulo \(998244353\). That is, if the expected weight is \(E\), output \(E \bmod 998244353\).

A generating function derivation (for insight)

For any fixed subarray of length \(k\), one may show that the sum of \(f_A(l,r)\) over all possible choices of the subarray is given by

[ F(k) = k! \cdot [t^k]\ \prod_{x=1}^{M} \Bigl(1 + x t \exp(x t)\Bigr), ]

where ([t^k]) means the coefficient of (t^k). Since every subarray of fixed length (k) is equally likely and there are (n-k+1) subarrays of length (k), the expected weight is given by

[ E = \sum_{k=1}^{n} (n-k+1) \cdot \frac{F(k)}{M^k} \pmod{998244353}. ]

You are required to compute this expected value modulo \(998244353\).

inputFormat

The input consists of a single line with two integers \(n\) and \(M\) (separated by a space):

1. \(n\) — the length of the sequence.
2. \(M\) — the maximum value for each element in the sequence (each \(A_i \in [1, M]\)).

\(1 \le n \le 2000\) and \(1 \le M \le 2000\).

outputFormat

Output a single integer: the expected weight \(E\) modulo \(998244353\).

sample

3 3

145