题目描述

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