「PMOI-2」简单构造题

某次模拟赛中，NaCly\_Fish 遇见这样一道题： **** 定义一个长度为 $n$ 的序列 $A$ 的权值为： $$\sum_{l=1}^n\sum_{r=l}^n f_A(l,r)$$ 其中 $f_A(l,r)$ 就是在 $A$ 的区间 $[l,r]$ 中，「所有**在该区间内出现过的**元素出现次数的乘积」再乘上「区间内所有元素的乘积」。 要求构造一个长为 $n$ 的序列，其中每个元素都是 $[1,m]$ 中的整数，最大化其权值。 **** 她并不会，只好均匀随机 $n$ 个 $[1,m]$ 中的整数组成一个数列，然后输出其权值。 当然，她的这份程序一分都没拿到；但她想知道，生成出的序列期望权值是多少。 为了防止精度问题，答案需要对 $998244353$ 取模。

一行两个正整数 $n,m$。

输出一行一个整数，表示答案。

3 2

623902740

5 3

887328630

80 233

913763047

114514 19260817

850727003

【样例一解释】 显然有 $8$ 种可能的序列： $[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]$。 权值分别为 $10,12,12,23,12,17,23,46$，期望值就是 $\frac{155}{8}$。 【样例二解释】 期望值是 $\frac{76842}{243}$。 【数据范围】 **本题采用捆绑测试**。 - 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）：无特殊限制。 对于 $100\%$ 的数据满足，$1\le n \le 2 \times 10^5$，$1\le m \le 10^8$。