AT_utpc2022_c.Nim is Time-consuming

UT 君和 PC 君正在玩一种叫做 Nim 的游戏。对于 $N$ 个正整数 $A_1, A_2, \ldots, A_N$，$\mathrm{Nim}(A_1, A_2, \ldots, A_N)$ 描述如下游戏：

• 有 $N$ 堆石子，第 $i$ 堆有 $A_i$ 个石子（$1 \le i \le N$）。UT 君先手，二人依次轮流进行如下操作：

• （操作） 选择任意一个剩下石子数不少于 $1$ 的堆，从中取走至少 $1$ 个石子。

• 当所有石子被取完时，游戏结束。最后一次操作的人获胜，另一方失败。

• 从游戏开始到结束，两人操作的总次数为 $T$。获胜者得到 $10^{100} - T$ 分，失败者得到 $T - 10^{100}$ 分。

满足 $1 \le A_i \le M\ (1 \le i \le N)$ 的所有长度为 $N$ 的整数序列 $(A_1, A_2, \ldots, A_N)$ 一共有 $M^N$ 种。对于每一种，这两个人都玩一局 $\mathrm{Nim}(A_1, A_2, \ldots, A_N)$。

当双方在所有游戏中都采取最优策略以最大化自己获得的分数时，这 $M^N$ 场游戏的操作总数是多少？结果可能非常大，请输出其除以 $998244353$ 的余数。

输入为一行，包含两个整数：

$N$ $M$

输出一行，表示所求答案对 $998244353$ 取模的结果。

样例解释 1

两个人会玩如下 $4$ 种游戏：

• $\mathrm{Nim}(1, 1)$
• $\mathrm{Nim}(1, 2)$
• $\mathrm{Nim}(2, 1)$
• $\mathrm{Nim}(2, 2)$

对于每种，双方都采取最佳策略，则每局的操作次数分别为 $2$、$3$、$3$、$4$，总和为 $12$。应输出 $12$。

样例解释 4

请输出答案对 $998244353$ 取模的结果。

约束条件

• 输入均为整数
• $1 \le N \le 10^9$
• $1 \le M \le 500$

由 ChatGPT 5 翻译