5201. Kaleidoscope

单点时限: 1.0 sec

内存限制: 1024 MB

现在你有无穷多的 $1\times 2$ 大小和 $2\times 2$ 大小的棋子,其中 $1\times 2$ 大小的棋子可以横着占据 $1$ 行 $2$ 列的格子,也可以竖着占据 $2$ 行 $1$ 列的格子。

我们的棋盘不再是一个 $2$ 行,但列数不定的棋盘,而是一个 $n$ 行 $m$ 列的棋盘。

请你输出铺满当前棋盘的方案总数。

由于方案总数可能很大,请你输出方案总数对 $998244353$ 取模后的值。

输入格式

输入仅一行两个整数 $n,m$ ($1 \leq n \leq 5000$,$1\leq m \leq 10$),分别表示当前棋盘的行数和列数。

输出格式

输出一个整数,表示铺满当前棋盘的方案总数对 $998244353$ 取模后的值。

样例

Input
1 2
Output
1
Input
2 3
Output
5

提示

下图为 $n=2,m=3$ 时对应的可能的铺棋子方案。

100 人解决,131 人已尝试。

115 份提交通过,共有 330 份提交。

3.4 EMB 奖励。

创建: 1 年,3 月前.

修改: 1 年,3 月前.

最后提交: 1 月,2 周前.

来源: N/A

题目标签