分数: 600 点
问题陈述
有一个网格 H 水平行和 W 垂直列,以及 (2 \times H) 件。 我们考虑使用它们的以下游戏。
两名玩家轮流轮流。 游戏进行如下。
- 在初始状态下,每行包含第一个玩家朝左的一颗棋子和第二个玩家朝右的一颗棋子。
- 两名玩家交替推进他们的一颗棋子。
- 最先无法采取行动的玩家失败,另一位玩家获胜。
让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。 允许以下动作:
- 第一个玩家可以移动棋子 (i,j) to (i,k) if k \lt j 并且没有一个 (i,k),(i,k+1),\dots,(i,j-1) 包含任一玩家的棋子。
- 第二个玩家可以移动棋子 (i,j) to (i,k) if k \gt j 并且没有一个 (i,j+1),(i,j+2),\dots,(i,k) 包含任一玩家的棋子。
例如,在下图中,在 3\times 9 格子,第一个玩家的棋子位于 (1,7),(2,1),(3,4),第二个玩家的棋子位于 (1,3),(2,7),(3,5).
第一个玩家可以将棋子移动到 (1,7) to (1,4),(1,5),或 (1,6),以及位于 (3,4) to (3,1),(3,2),或 (3,3)。 第一个玩家不能移动棋子 (2,1).

目前,网格上没有棋子。 有 \left\lbrace W(W-1)\right\rbrace^H 将第一个玩家的一个棋子和第二个玩家的一个棋子放置在每行中的方法,以便不会将两个棋子放置在同一个方格上。 其中有多少人满足以下条件? 求计数模数 998244353.
- 当他们从初始状态开始以最佳方式玩游戏时,第一个玩家获胜。
约束
- 1 \leq H \leq 8000
- 2 \leq W \leq 30
- H 和 W 是整数。
输入
输入由标准输入按以下格式给出:
H W
输出
打印答案。
示例输入 1
1 3
示例输出 1
2
如果满足以下条件,第一位玩家可以获胜:
- 第一个玩家的棋子放置在 (1, 3),第二个玩家的棋子放在 (1, 1);或
- 第一个玩家的棋子放置在 (1, 2),第二个玩家的棋子放在 (1, 3).
示例输入 2
9 9
示例输出 2
583962987
示例输入 3
265 30
示例输出 3
366114675