← 返回题目列表

AtCoder · utpc2022_c

C. Nim 很耗时

中文机器翻译题面 查看原题

配点 : 100 点

問題文

UT和PC正在玩一款名为Nim的游戏。N 正整数 是 A_1, A_2,\ldots, A_N ,\mathrm{Nim}(A_1, A_2, \ldots, A_N) 指以下游戏。

  • 由几块石头组成 有 N 山,一开始 i\ (1\le i\le N) 第一座山有 A_i 石头。 UT 从你开始,2 人们轮流执行以下操作。 重复 1 次。
    • (操作) 石头 1 或更多剩余山脉 1 选择一项。那座山上的石头 删除 1 或更多。
  • 当所有棋子都被移走时,游戏结束,最后一步的玩家获胜,另一位玩家失败。
  • 从比赛开始到比赛结束 2 计算一个人执行的操作总数。 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 方法有很多,但对于所有方法来说,2 人 1 次 播放 \mathrm{Nim}(A_1, A_2, \ldots, A_N) 。

当每个人的行动都最大化所有游戏中获得的总积分时,这些 M^N 游戏中的总操作次数是多少?答案可能非常大,所以998244353 求余数。

制約

  • 所有输入均为整数
  • 1 \le N \le 10^{9}
  • 1 \le M \le 500

入力

输入是按以下格式从标准输入给出的。

N M

出力

答案 1 行输出。


入力例 1

2 2

出力例 1

12

2 以下人员 4 玩两个游戏。

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

如果每个人都尽力而为,则每场比赛的操作次数将为 2、3、3、4 。是这些的总和 12 。


入力例 2

4 5

出力例 2

6748

入力例 3

1 222

出力例 3

222

入力例 4

987654321 456

出力例 4

897555885

答案值 请打印除以 998244353 后的余数。