无吃子香车棋

题目描述

我们有一个 $H$ 行 $W$ 列的网格，以及 $2 \times H$ 枚棋子。考虑用这些棋子进行的如下游戏。

两名玩家轮流行动。游戏按以下方式推进。

初始状态下，每一行都有一枚先手玩家的棋子朝左摆放，以及一枚后手玩家的棋子朝右摆放。

两名玩家轮流推进自己的一枚棋子。

率先无法行动的玩家失败，另一名玩家获胜。

设 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。允许以下移动：

• 先手玩家可以将位于 $(i,j)$ 的棋子移动到 $(i,k)$，当且仅当 $k \lt j$ 且 $(i,k),(i,k+1),\dots,(i,j-1)$ 中没有任何一枚棋子。
• 后手玩家可以将位于 $(i,j)$ 的棋子移动到 $(i,k)$，当且仅当 $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)$ 处的棋子移动到 $(1,4),(1,5)$ 或 $(1,6)$，将 $(3,4)$ 处的棋子移动到 $(3,1),(3,2)$ 或 $(3,3)$。先手玩家无法移动 $(2,1)$ 处的棋子。

现在网格上还没有任何棋子。在每一行各放置一枚先手棋子与一枚后手棋子、且两枚棋子不在同一格子的摆放方式共有 $\left\lbrace W(W-1)\right\rbrace^H$ 种。其中有多少种满足以下条件？求答案对 $998244353$ 取模。

从该初始状态开始双方都最优地玩这个游戏时，先手玩家获胜。

输入格式

输入按以下格式从标准输入给出：

$H$ $W$

输出格式

输出答案。

样例

1 3

2

先手玩家在以下情况下可以获胜：

• 先手棋子放在 $(1,3)$，后手棋子放在 $(1,1)$；或
• 先手棋子放在 $(1,2)$，后手棋子放在 $(1,3)$。

9 9

583962987

265 30

366114675

数据范围

• $1 \le H \le 8000$
• $2 \le W \le 30$
• $H$ 和 $W$ 是整数