当前没有测试数据。

Ex - 不捕获的长枪游戏

得分：$600$ 分

题目描述

有一个 $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$ 取模。

• 按照初始状态从最优方案进行游戏，第一名玩家获胜。

约束

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

输入

从标准输入读入数据，数据格式如下：

$H$ $W$

输出

输出答案。

1 3

2

对于此例，第一名玩家可以获胜的有以下情况：

• 第一名玩家的棋子放在 $(1, 3)$ 处，第二名玩家的棋子放在 $(1, 1)$ 处；或
• 第一名玩家的棋子放在 $(1, 2)$ 处，第二名玩家的棋子放在 $(1, 3)$ 处。

9 9

583962987

265 30

366114675