P10681 [COTS 2024] Odd-Even Matrix Tablica
Background
Translated from [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T2. $\texttt{1s,1G}。$
Description
Consider an $N \times M$ matrix $A$ that contains only $0$ and $1$.
We call a matrix good if it satisfies the following conditions:
- $\forall 1\le i\le N$, $\displaystyle \sum_{j=1}^M A_{i,j}\in \{1,2\}$;
- $\forall 1\le j\le M$, $\displaystyle \sum_{i=1}^N A_{i,j}\in \{1,2\}$.
Find the number of good matrices with $N$ rows and $M$ columns, modulo $(10^9+7)$.
Input Format
The input consists of one line with two positive integers, $N, M$.
Output Format
Output one line with one integer, the result modulo $(10^9+7)$.
Explanation/Hint
#### Sample Explanation
Sample $1$ is explained as shown in the figure.
#### Constraints
For $100\%$ of the testdata, $1\le N,M\le 3\, 000$.
| Subtask ID | Score | Constraints |
|:-----:|:------:|:-------:|
| $1$ | $10$ | $N, M \leq 6$ |
| $2$ | $18$ | $N, M \leq 50$ |
| $3$ | $31$ | $N, M \leq 200$ |
| $4$ | $41$ | No additional constraints |
Translated by ChatGPT 5