Score : $600$ points

问题陈述

存在一个包含 $H$ 行和 $W$ 列的网格，以及 $(2 \times H)$ 个棋子。我们将使用它们进行以下游戏。

• 游戏开始时，每一行包含一个面向左边的第一位玩家的棋子和一个面向右边的第二位玩家的棋子。
• 两位玩家交替移动他们的棋子。
• 首先无法移动棋子的玩家输掉比赛，另一位玩家获胜。

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

• 第一位玩家可以将位于 $(i,j)$ 的棋子移动至 $(i,k)$，如果 $k < j$ 且 $(i,k),(i,k+1),\dots,(i,j-1)$ 中均不包含任何玩家的棋子。
• 第二位玩家可以将位于 $(i,j)$ 的棋子移动至 $(i,k)$，如果 $k > 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$ 后的结果。

• 当他们从该初始状态开始，以最优策略进行游戏时，第一位玩家获胜。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a grid with $H$ horizontal rows and $W$ vertical columns, and $(2 \times H)$ pieces. We consider the following game using them.
Two players take alternating turns. The game progresses as follows.

• In the initial state, every row contains one piece of the first player facing left and one piece of the second player facing right.
• The two players alternately advance one of their pieces.
• The player who is first to be unable to make a move loses, and the other player wins.

Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left. The following moves are allowed:

• The first player can move a piece at $(i,j)$ to $(i,k)$ if $k \lt j$ and none of $(i,k),(i,k+1),\dots,(i,j-1)$ contains a piece of either player.
• The second player can move a piece at $(i,j)$ to $(i,k)$ if $k \gt j$ and none of $(i,j+1),(i,j+2),\dots,(i,k)$ contains a piece of either player.

For example, in the figure below, on a $3\times 9$ grid, the first player's pieces are at $(1,7),(2,1),(3,4)$, and the second player's pieces are at $(1,3),(2,7),(3,5)$.
The first player can move the piece at $(1,7)$ to $(1,4),(1,5)$, or $(1,6)$, and the piece at $(3,4)$ to $(3,1),(3,2)$, or $(3,3)$. The first player cannot move the piece at $(2,1)$.

Currently, there is no piece on the grid. There are $\left\lbrace W(W-1)\right\rbrace^H$ ways to place one piece of the first player and one piece of the second player in each row, so that no two pieces are placed at the same square. How many of them satisfy the following condition? Find the count modulo $998244353$.

• When they play the game optimally from that initial state, the first player wins.

Constraints

• $1 \leq H \leq 8000$
• $2 \leq W \leq 30$
• $H$ and $W$ are integers.

Input

Input is given from Standard Input in the following format:

$H$ $W$

Output

Print the answer.

Sample Input 1

1 3

Sample Output 1

2

The first player can win if:

• the first player's piece is placed at $(1, 3)$, and the second player's piece is placed at $(1, 1)$; or
• the first player's piece is placed at $(1, 2)$, and the second player's piece is placed at $(1, 3)$.

Sample Input 2

9 9

Sample Output 2

583962987

Sample Input 3

265 30

Sample Output 3

366114675

update @ 2024/3/10 11:14:07