Mujin Programming Challenge 2018

H - タイル張り


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 1024MB

配点 : 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 通りが条件を満たします。


入力例 2

3 4

出力例 2

550

入力例 3

5 100

出力例 3

655553721

Submit提出する