#P18490. T Tile Placement Counting
T Tile Placement Counting
T Tile Placement Counting
一头鲸鱼优雅地游着,尾鳍露出水面。这是一道铺砖问题。
用如下图所示的 T 形四连块,完全铺满一个 的方格。求不同铺法的数量,答案对 取模。

铺砖时须满足:
- 每块瓷砖沿方格放置;
- 瓷砖不能伸出方格外;
- 不同瓷砖不能覆盖同一个格子;
- 不能留下未被瓷砖覆盖的格子。
允许旋转瓷砖,不区分瓷砖的正反面,也不区分不同的瓷砖。仅在整体旋转或镜像后才能重合的两种铺法,仍视为不同铺法。
输入格式
H W
所有输入值均为整数,且满足:
- ;
- 。
本题单组输入。不保证长、宽是 4 的倍数。
输出格式
输出不同铺法的数量对 取模后的整数。
样例 1
4 4
2
恰有下图所示的两种铺法。

样例 2
2 8
0
不存在满足要求的铺法。
样例 3
12 3456
491051233