#P18490. T Tile Placement Counting

T Tile Placement Counting

T Tile Placement Counting

一头鲸鱼优雅地游着,尾鳍露出水面。这是一道铺砖问题。

用如下图所示的 T 形四连块,完全铺满一个 H×WH\times W 的方格。求不同铺法的数量,答案对 998244353998244353 取模。

原题T形四连块

铺砖时须满足:

  • 每块瓷砖沿方格放置;
  • 瓷砖不能伸出方格外;
  • 不同瓷砖不能覆盖同一个格子;
  • 不能留下未被瓷砖覆盖的格子。

允许旋转瓷砖,不区分瓷砖的正反面,也不区分不同的瓷砖。仅在整体旋转或镜像后才能重合的两种铺法,仍视为不同铺法。

输入格式

H W

所有输入值均为整数,且满足:

  • 1≤H≤301\le H\le30;
  • 1≤W≤10181\le W\le10^{18}。

本题单组输入。不保证长、宽是 4 的倍数。

输出格式

输出不同铺法的数量对 998244353998244353 取模后的整数。

样例 1

4 4
2

恰有下图所示的两种铺法。

原题4×4两种铺法

样例 2

2 8
0

不存在满足要求的铺法。

样例 3

12 3456
491051233