配点 : 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 后的余数。