AT_mujin_pc_2018_h.タイル張り

在一个 $H\times W$ 的网格中，将所有格子涂成黑色或白色，要求满足以下条件：能够放置若干个 $1\times 2$ 的瓷砖（如有需要，可以旋转瓷砖），使得：

• 瓷砖不能超出网格边界，且不同瓷砖之间不能重叠。
• 每个瓷砖恰好覆盖网格中的 $2$ 个格子。
• 所有被涂成白色的格子，恰好被 $1$ 块瓷砖覆盖。
• 所有被涂成黑色的格子，不能被瓷砖覆盖。

请计算满足条件的涂色方案数，并对 $998244353$ 取模。

输入从标准输入读取，格式如下：

$H$ $W$

输出满足条件的涂色方案数。

限制

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

样例解释 1

全部格子涂成白色的方案有 $1$ 种，全部格子涂成黑色的方案有 $1$ 种，将相邻的 $2$ 个格子涂成黑色，其余 $2$ 个格子涂成白色的方案有 $4$ 种，共计 $6$ 种方案满足条件。

由 ChatGPT 4.1 翻译