Background

Translated from Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D1T2. $\texttt{1s,1G}。$

Problem 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)$.

2 2

7

3 3

102

15 20

415131258

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$.

Translated by ChatGPT 5