题目描述

某次模拟赛中，NaCly_Fish 遇见这样一道题：

定义一个长度为 $n$ 的序列 $A$ 的权值为：

其中 $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$。