#2833. 「JOISC 2018 Day 1」帐篷

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: fbhou

题目描述

译自 JOISC 2018 Day1 T3「テント / 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 i\le H,1\le j_{1} < j_{2}\le W) 上都有帐篷,那么格子 (i,j_{1}) 上的帐篷出入口必须朝东,而格子 (i,j_{2}) 上的帐篷出入口必须朝西。

JOI 君想知道在露营地上搭起至少一顶帐篷的合法方案数。两种方案被认为是不同的,当且仅当有至少一个格子的状态(即是否存在帐篷或帐篷出入口的朝向)不同。

任务

给出露营地的相关信息,请求出在露营地上搭起至少一顶帐篷的合法方案数,对 1000000007 取模。

输入格式

仅一行两个以空格分开的整数 H W ,表示 JOI 君经营的露营地有 H W 列。

输出格式

输出一行,仅一个整数,表示在露营地上搭起至少一顶帐篷的合法方案数对 1000000007 取模的余数。

样例

输入样例 1

1 2

输出样例 1

9

样例说明 1

如下图所示,共有 9 种搭帐篷的方式。图中字母 E,W,S,N 分别代表出入口朝向东、西、南、北的帐篷。

输入样例 2

4 3

输出样例 2

3252

输入样例 3

100 100

输出样例 3

561068619

数据范围与提示

子任务 1(48 分) \ 1\le H, W\le 300
子任务 2(52 分) \ 1\le H, W\le 3000