【2018】填数游戏：统计满足路径约束的n×m 01矩阵填法数

题目描述

小D特别喜欢玩游戏。这一天，他在玩一款填数游戏。 这个填数游戏的棋盘是一个$n \times m$的矩形表格。玩家需要在表格的每个格子中填入一个数字（数字0或者数字1），填数时需要满足一些限制。 下面我们来具体描述这些限制。 为了方便描述，我们先给出一些定义：

• 我们用每个格子的行列坐标来表示一个格子，即（行坐标，列坐标）。（注意：行列坐标均从0开始编号）
• 合法路径P：一条路径是合法的当且仅当：
  1. 这条路径从矩形表格的左上角的格子$(0,0)$出发，到矩形的右下角格子$(n-1,m-1)$结束；
  2. 在这条路径中，每次只能从当前的格子移动到右边与它相邻的格子，或者从当前格子移动到下面与它相邻的格子。 例如：在2×2的矩形中，只有两条路径是合法的，它们分别是$P_1: (0,0) \to (0,1) \to (1,1)$和$P_2: (0,0) \to (1,0) \to (1,1)$。 对于一条合法的路径P，我们可以用一个字符串$w(P)$来表示，该字符串的长度为$n + m - 2$，其中只包含字符R或者字符D，第i个字符记录了路径P中第i步的移动方法，R表示移动到当前格子右边与它相邻的格子，D表示移动到当前格子下面与它相邻的格子。例如，对于上述2×2矩形中的路径$P_1$，有$w(P_1) = "RD"$；而对于路径$P_2$，有$w(P_2) = "DR"$。 同时，将每条合法路径P经过的每个格子上填入的数字依次连接后，会得到一个长度为$n + m - 1$的01字符串，记为$s(P)$。例如，如果我们在格子$(0,0)$和$(1,0)$上填入数字0，在格子$(0,1)$和$(1,1)$上填入数字1，那么对于路径$P_1$，我们可以得到$s(P_1) = "011"$，对于路径$P_2$，有$s(P_2) = "001"$。 游戏要求小D找到一种填数字0、1的方法，使得对于两条路径$P_1, P_2$，如果$w(P_1) > w(P_2)$（字符串字典序比较），那么必须$s(P_1) \leq s(P_2)$。小D想知道有多少种填数字的方法满足游戏的要求？ 由于答案可能很大，你需要输出答案对$10^9 + 7$取模的结果。

输入描述

输入文件共一行，包含两个正整数$n, m$，由一个空格分隔，表示矩形的大小。其中$n$表示矩形表格的行数，$m$表示矩形表格的列数。

输出描述

输出共一行，包含一个正整数，表示有多少种填0、1的方法能满足游戏的要求，结果对$10^9+7$取模。

样例

输入样例1：

2 2

输出样例1：

12

输入样例2：

3 3

输出样例2：

112

输入样例3：

5 5

输出样例3：

7136

样例解释

对于2×2棋盘，共有12种填数方法满足要求。

数据规模与约定

测试点编号	$n \leq$	$m \leq$
1~4	3	3
5~10	2	1000000
11~13	3	1000000
14~16	8	8
17~20	8	1000000