102657: [AtCoder]ABC265 Ex - No-capture Lance Game

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

问题描述

有一个包含$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

1 3

样例输出1

2

第一玩家可以赢如果：

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

样例输入2

9 9

样例输出2

583962987

样例输入3

265 30

样例输出3

366114675