Counting Good Matrices

A good matrix is defined as an \(N\times M\) binary matrix \(A\) (with entries 0 or 1) satisfying:

• For every row \(1\le i \le N\), \(\displaystyle \sum_{j=1}^M A_{i,j} \in \{1,2\}\).
• For every column \(1\le j \le M\), \(\displaystyle \sum_{i=1}^N A_{i,j} \in \{1,2\}\).

Let \(T\) be the total number of 1’s in the matrix. Since the row sums are either 1 or 2, if we denote by \(r_1\) the number of rows with sum 1 and \(r_2\) the number of rows with sum 2, then \[ T=r_1+2r_2, \quad r_1+r_2=N. \] Similarly, if \(c_1\) is the number of columns with sum 1 and \(c_2\) the number of columns with sum 2, then \[ T=c_1+2c_2, \quad c_1+c_2=M. \] This forces \[ r_1=2N-T, \quad c_1=2M-T, \quad r_2=T-N, \quad c_2=T-M. \] Thus, a necessary condition is \[ \max(N, M)\le T\le \min(2N,2M). \]

The total number of good matrices is the sum over all valid \(T\) of

\[ \binom{N}{2N-T} \cdot \binom{M}{2M-T} \cdot f_{\text{fixed}}(T) \pmod{10^9+7}, \]

where \(f_{\text{fixed}}(T)\) is the number of ways to fill the matrix with fixed row and column margins. Namely, assume that the rows chosen to have sum 1 are fixed (and similarly the columns chosen to have sum 1 are fixed). Then the column margins are given by \(c_1=2M-T\) columns of 1 and \(c_2=T-M\) columns of 2, and the row margins are: the first \(r_1=2N-T\) rows must have sum 1 and the remaining \(r_2=T-N\) rows have sum 2. These entries must be assigned so that the column requirements are met.

This can be computed in two phases using dynamic programming:

• Phase 1 (Row Type 1): Process the first \(r_1\) rows (each must contribute exactly 1 one). If the current state is given by \((x,y)\), where \(x\) is the number of columns with remaining capacity 1 and \(y\) the number with remaining capacity 2, then a row of type 1 can be filled in one of two ways:
  • Pick one column among those of capacity 1. There are \(x\) ways; that column’s capacity becomes 0. New state: \((x-1,y)\).
  • Pick one column among those of capacity 2. There are \(y\) ways; that column’s capacity decreases from 2 to 1 (i.e. moves to the group with capacity 1). New state: \((x+1,y-1)\).
• Phase 2 (Row Type 2): Process the remaining \(r_2\) rows (each must contribute 2 ones). For a row of type 2 from state \((x,y)\), the possibilities are:
  • Choose two columns from those of capacity 1. This can be done in \(\binom{x}{2}\) ways. New state: \((x-2,y)\).
  • Choose one column of capacity 1 and one column of capacity 2. This can be done in \(x\times y\) ways. New state: \((x,y-1)\) (since the column from capacity 2 decreases to 1 while the column from capacity 1 becomes 0).
  • Choose two columns from those of capacity 2. This can be done in \(\binom{y}{2}\) ways. New state: \((x+2,y-2)\) (both chosen columns decrease from capacity 2 to 1).

The initial column state is \((c_1,c_2)=(2M-T, T-M)\) (since columns chosen to have sum 1 have initial capacity 1 and those with sum 2 have initial capacity 2). Finally, we want the final state to be \((0,0)\) (i.e. all column capacities must be exactly met).

Your task is to compute the number of good matrices modulo \(10^9+7\).

inputFormat

The input consists of a single line containing two integers \(N\) and \(M\) (representing the number of rows and columns respectively).

outputFormat

Output a single integer, the number of good matrices modulo \(10^9+7\).

sample

2 2

7