P14367 [JOISC 2018] 帐篷 / Tents

JOI 君经营着一个露营地。该露营地被划分为一个 $H$ 行 $W$ 列的矩形网格。行与东西方向平行，列与南北方向平行。从北往南第 $i$ 行、从东往西第 $j$ 列的区域称为区域 $(i, j)$。 JOI 君打算在部分区域搭建帐篷。每个帐篷必须恰好占据一个区域，且任意两个帐篷不得占据同一区域。 每个帐篷的入口朝向四个方向之一：北、南、东或西。露营地中所搭帐篷的入口方向必须满足以下条件： - 若两个区域 $(i_1, j)$ 和 $(i_2, j)$（其中 $1 \le i_1 < i_2 \le H$，$1 \le j \le W$）均被帐篷占据，则区域 $(i_1, j)$ 中帐篷的入口必须朝南，区域 $(i_2, j)$ 中帐篷的入口必须朝北。 - 若两个区域 $(i, j_1)$ 和 $(i, j_2)$（其中 $1 \le j_1 < j_2 \le W$，$1 \le i \le H$）均被帐篷占据，则区域 $(i, j_1)$ 中帐篷的入口必须朝东，区域 $(i, j_2)$ 中帐篷的入口必须朝西。 JOI 君对在露营地至少搭建一个帐篷的方案总数感到好奇。若存在某个区域，其帐篷状态（是否存在帐篷，或帐篷入口方向）在两种方案中不同，则这两种方案被视为不同。 **任务** 编写一个程序，计算满足题面所述条件的至少搭建一个帐篷的方案总数，对 $1\,000\,000\,007$ 取模后的余数。

从标准输入读取以下数据： - 输入第一行包含两个整数 $H$ 和 $W$，表示 JOI 君经营的露营地被划分为 $H$ 行 $W$ 列。

向标准输出写入一行。输出应包含满足题面所述条件的至少搭建一个帐篷的方案总数，对 $1\,000\,000\,007$ 取模后的余数。

### 样例 1 解释 如下图所示，共有 $9$ 种搭帐篷的方式。图中字母 $E,W,S,N$ 分别代表出入口朝向东、西、南、北的帐篷。 :::align{center}  ::: ### 数据范围 所有输入数据满足以下条件： - $1 \le H \le 3\,000$。 - $1 \le W \le 3\,000$。 ### 子任务 共有 2 个子任务。每个子任务的得分和附加约束如下： **子任务 1 [48 分]** - $1 \le H \le 300$。 - $1 \le W \le 300$。 **子任务 2 [52 分]** 无额外约束。