Problem Background

NOIP2018 Senior Group D2T2

Problem Description

Little D loves playing games. On this day, he was playing a number-filling game.

The board of this number-filling game is an $n \times m$ rectangular grid. The player needs to fill each cell in the grid with a digit (either $0$ or $1$), subject to certain constraints.

Here are the specific constraints:

For convenience, we first provide some definitions:

• We represent each cell with its row and column coordinates, i.e., (row coordinate, column coordinate). Note: Both row and column coordinates are zero-indexed.
• A valid path $P$: A path is valid if and only if:
  1. It starts from the top-left cell $(0,0)$ and ends at the bottom-right cell $(n - 1, m - 1)$;
  2. In this path, one can only move to the right adjacent cell or the bottom adjacent cell from the current cell.

For example, in the following grid, only two paths are valid, which are $P_1$: $(0,0) \to (0,1) \to (1,1)$ and $P_2$: $(0,0) \to (1,0) \to (1,1)$.

For a valid path $P$, we can represent it with a string $w(P)$ of length $n + m - 2$, which contains only the characters $\texttt R$ or $\texttt D$. The $i$-th character records the movement method of the $i$-th step in path $P$. $\texttt R$ indicates moving to the right adjacent cell, and $\texttt D$ indicates moving to the bottom adjacent cell. For example, for path $P_1$ in the above figure, we have $w(P_1) = \texttt$; for path $P_2$, we have $w(P_2) = \texttt$.

Additionally, concatenating the digits filled in each cell along a valid path $P$ results in a $01$ string of length $n + m - 1$, denoted as $s(P)$. For example, if we fill the digits $0$ in cells $(0,0)$ and $(1,0)$, and $1$ in cells $(0,1)$ and $(1,1)$ (see the red digits in the figure), then for path $P_1$, we get $s(P_1) = 011$, and for path $P_2$, we get $s(P_2) = 001$.

The game requires Little D to find a way to fill the digits $0$ and $1$ such that for any two paths $P_1$ and $P_2$, if $w(P_1) > w(P_2)$, then it must be that $s(P_1) \leq s(P_2)$. We say string $a$ is smaller than string $b$ if and only if the lexicographical order of string $a$ is less than that of string $b$. However, finding just one method does not satisfy Little D's curiosity; he wants to know how many ways there are to fill the digits to meet the game's requirements.

Little D's abilities are limited, and he hopes you can help him solve this problem, i.e., how many ways are there to fill the digits $0$ and $1$ to meet the requirements of the game? Since the answer may be very large, you need to output the answer modulo $10^9 + 7$.

Input Format

The input file contains one line with two positive integers $n$ and $m$, separated by a space, representing the size of the rectangle. $n$ denotes the number of rows, and $m$ denotes the number of columns.

Output Format

The output contains one line with a positive integer, representing the number of ways to fill the digits $0$ and $1$ to meet the game's requirements, modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

2 2

Sample Output #1

12

Sample Input #2

3 3

Sample Output #2

112

Sample Input #3

5 5

Sample Output #3

7136

Notes/Hints

Sample Explanation

Data Size and Constraints

见题面 Input 部分

见题面 Output 部分