题目描述

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 2

9

4 3

3252

100 100

561068619

提示

样例 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 分]

无额外约束。