You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

观测塔建造

题目背景

题目描述

小明正在玩一款星球大战类型的游戏，这个游戏里有一片$n*m$的空地，小明需要在上面建造一些观测塔。每个观测塔占地一个$1*1$的小方格，并且有它的观测方向（只能是水平或者竖直方向，即上下左右）。小明有两种观测塔，这两种观测塔能正常工作的要求不一样。

单体观测塔：要求它所在的行列里没有其他的观测塔才可以正常工作，观测方向不作限制；

双子观测塔：由一对位于同一行或者同一列的观测塔构成，要求这一对观测塔互相能够观测到对方，且它们所在的行列内没有其他的观测塔，才可以正常工作。

假设小明手上有无限资源，可以无限建造观测塔，他想知道自己有多少种在这片空地上建造观测塔的方案，使得所有观测塔都可以正常工作。两种方案不同，当且仅当观测塔的布置不同，或者观测塔的布置相同但存在一个观测塔的观测方向不同。

注：不能一座观测塔都不建造，最终答案对1000000007取模。

输入格式

一行两个正整数$n$和$m$。

输出格式

一个正整数表示答案。

样例 #1

样例输入 #1

1 2

样例输出 #1

9

提示

样例解释1：

建造1个单体观测塔，可以建造在两个空格的任一个，且各有4种朝向，共8种方案；

建造1个双子观测塔，两个空格都要占据且观测方向必须互相能看到，只有1种方案；

故共有9种方案。

具体列表如下：

X↑ X↓ X← X→ ↑X ↓X ←X →X →←

数据范围

对$40\%$的数据，$1≤n,m≤300$；

对$100\%$的数据，$1≤n,m≤3000$。