Filling the Board Game

Little D loves playing games. One day, he tries a number‐filling game on a board. The board is an \( n\times m \) rectangular grid. In each cell you must put either a \(0\) or a \(1\). However, the filling must satisfy a special condition described below.

Let us first define some notions. Each cell is denoted by its coordinates \((i,j)\) with \(0\le i\le n-1\) and \(0\le j\le m-1\). A legal path \(P\) is a sequence of cells satisfying the following conditions:

1. The path starts at the top–left cell \((0,0)\) and ends at the bottom–right cell \((n-1,m-1)\).
2. Each move is either a step to the right (denoted by the letter R) or a step down (denoted by D); in other words, from cell \((i,j)\) you may only move to \((i,j+1)\) or \((i+1,j)\).

Each legal path \(P\) can be encoded in two ways:

• Its route string \(w(P)\): a string of length \(n+m-2\) consisting of characters R and D. For example, in a \(2\times2\) board the two legal paths have \(w(P_1)=RD\) and \(w(P_2)=DR\) (since comparing letters in ASCII, we have \(D< R\)).
• Its value string \(s(P)\): the binary string obtained by concatenating the digits (\(0\) or \(1\)) written in the cells along \(P\) (thus of length \(n+m-1\)).

The game requires that the filling of the board must be such that for any two legal paths \(P_1\) and \(P_2\) the following condition holds:

[ \text{if } w(P_1)>w(P_2) \text{ then } s(P_1)\le s(P_2), ]

where the comparison of strings is in lexicographical order (compare character by character using the usual order of characters in ASCII, so that \(D< R\) and for binary strings \(0<1\)).

Your task is to count the number of ways to fill the \( n\times m \) board with \(0\) and \(1\) so that the above condition holds. Since the answer might be large, output it modulo \(10^9+7\).

---

Observation and Reformulation:

It can be shown that the condition is equivalent to the following local constraint on the board. For every \(2\times2\) subgrid with cells

[ \begin{array}{cc} a & b\ c & d \end{array} ]

we must have

[ b\le c. ]

Indeed, consider the two legal paths in a (2\times2) board: one gives (s(P_1)=(a,b,d)) and the other (s(P_2)=(a,c,d)). Since (w(P_1)=RD > DR=w(P_2)), the required condition is ( (a,b,d)\le (a,c,d)) which holds if and only if (b\le c).

Thus, the problem reduces to counting the number of \(n\times m\) binary matrices \(A=[a_{i,j}]\) (with \(a_{i,j}\in\{0,1\}\)) that satisfy for every \(0\le i\le n-2\) and \(0\le j\le m-2\):

[ a_{i,j+1} \le a_{i+1,j}. ]

Input: The input consists of two integers \(n\) and \(m\) representing the number of rows and columns respectively.

Output: Output one integer, the number of valid fillings modulo \(10^9+7\).

inputFormat

The first and only line of input contains two integers \(n\) and \(m\) (for example, \(1 \le n, m \le 10\)), separated by a space.

outputFormat

Output a single integer: the number of valid ways to fill the board, taken modulo \(10^9+7\).

sample

2 2

12