Problem Background

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

Problem Description

Consider a matrix $A$ of size $N \times M$ containing only $0$s and $1$s.

A matrix is considered good if it satisfies the following conditions:

• For all $1 \le i \le N$, $\displaystyle \sum_{j=1}^M A_{i,j} \in \{1, 2\}$;
• For all $1 \le j \le M$, $\displaystyle \sum_{i=1}^N A_{i,j} \in \{1, 2\}$.

Determine the number of good matrices of size $N \times M$, modulo $(10^9 + 7)$.

Input Format

The input consists of a single line containing two positive integers, $N$ and $M$.

Output Format

Output a single integer, representing the answer modulo $(10^9 + 7)$.

Sample Input and Output

Sample Input #1

2 2

Sample Output #1

7

Sample Input #2

3 3

Sample Output #2

102

Sample Input #3

15 20

Sample Output #3

415131258

Notes

Sample Explanation

The explanation for Sample $1$ is illustrated in the following image:

Data Range

For $100\%$ of the data, $1 \le N, M \le 3,000$.

见题面 Input 部分

见题面 Output 部分