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 翻译