题目内容

有一个 $r$ 行 $c$ 列的矩形网格，每个格子必须被涂成红色或蓝色。 上下左右相邻且颜色相同的格子可以相互连通。由连通关系形成的极大同色连通区域称为一个“色块”。 如果一个色块包含的格子个数是奇数，则称该色块是“优美的”。 现在你需要求出：一共有多少种给网格涂色的方案，使得网格中出现的每一个色块都是优美的？

约束条件：

• 行数 $r$ 和列数 $c$ 均为正整数。
• 总格子数不超过 $16$，即 $1 \le r \times c \le 16$。

输入描述

第一行包含两个整数 $r$ 和 $c$，分别表示网格的行数和列数。

输出描述

输出一个整数，表示所有色块都优美的涂色方案总数。

样例1

输入

1 2

输出

2

说明

在 $1 \\times 2$ 的网格中，共有 $2^2 = 4$ 种涂色方案。枚举所有方案：

• 红红：两个红色格子相邻，形成大小为 2 的连通块（偶数），不合法。
• 蓝蓝：同样形成大小为 2 的偶数连通块，不合法。
• 红蓝：左右颜色不同，产生两个大小为 1 的连通块，都是奇数，合法。
• 蓝红：同样两个大小为 1 的连通块，合法。 因此合法方案总数为 2。

样例2

输入

1 3

输出

4

说明

在 $1 \\times 3$ 的网格中，共有 $2^3 = 8$ 种方案。每个极大同色连通块的大小必须为奇数。 枚举所有合法方案：

• 红红红：一个大小为 3 的红色连通块，合法。
• 蓝蓝蓝：一个大小为 3 的蓝色连通块，合法。
• 红蓝红：三个大小均为 1 的连通块，合法。
• 蓝红蓝：三个大小均为 1 的连通块，合法。 其他方案（如红红蓝、红蓝蓝等）均会产生大小为 2（偶数）的连通块，不合法。故答案为 4。

样例3

输入

2 2

输出

10

说明

$2 \\times 2$ 网格共 $2^4 = 16$ 种方案。连通块大小只可能为 1、2、3 或 4，偶数大小不允许。

• 全红或全蓝：大小为 4（偶数），不合法。
• 三红一蓝：红色块大小为 3，蓝色为 1，均为奇数。有 $4$ 种方式选择蓝色的位置，均合法。
• 三蓝一红：同理有 $4$ 种合法方案。
• 两红两蓝：若同色相邻则产生大小为 2 的块，非法；只有红、蓝分别占据对角线（同色不相邻）时，形成四个大小为 1 的块，共 $2$ 种方案。 所有合法方案数：$4 + 4 + 2 = 10$。