← 返回题目列表

AtCoder · mujin_pc_2018_h

H. 平铺

中文机器翻译题面 查看原题

配点 : 1000 点

問題文

H\times W 的所有方块涂成白色或黑色的方法, 从而满足以下条件 计算可以放置 1\times 2 的多个图块(如有必要,旋转一些图块)的方式数量。 除以 998244353 后求余数。

  • 瓷砖不得超出网格,并且不同的瓷砖不得重叠。
  • 所有图块都完全位于网格上。 2 完全覆盖正方形。
  • 所有涂成白色的方块都是 被 1 瓷砖覆盖。
  • 所有涂成黑色的方块都没有被瓷砖覆盖。

制約

  • 1 \leq H \leq 5
  • 1 \leq W \leq 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

H W

出力

输出满足条件的彩色线的数量。


入力例 1

2 2

出力例 1

6

将所有方块涂成白色 1 正如预期的那样,将所有方块涂成黑色。 1 街道,相邻 2 将方块涂成黑色并填充剩余的部分 2 将方块涂成白色 4 街道总和 6 Street 满足条件。


入力例 2

3 4

出力例 2

550

入力例 3

5 100

出力例 3

655553721