No.1846 Good Binary Matrix
Problem Statement
You are given integers $H,W$. An $H \times W$ matrix $A$ satisfying the following conditions is called a good matrix.
- Every element of the matrix is $0$ or $1$.
- There is no row or column whose elements are all $0$. That is,
- for every $1\leq i\leq H$, there exists $1\leq j \leq W$ such that $A_{i,j}=1$.
- for every $1\leq j \leq W$, there exists $1\leq i \leq H$ such that $A_{i,j}=1$.
Find the number of possible good matrices $A$. Since the answer can be very large, output it modulo $(10^{9}+7)$.
Constraints
- $1\leq H,W \leq 10^{6}$
- All inputs are integers.
Input
$H \; W$
Output
Output the answer modulo $(10^{9}+7)$. Print a newline at the end.
Sample
Sample 1
Input
2 2
Output
7
The following $7$ matrices are good matrices. $ A = \begin{pmatrix}0&1 \\ 1 & 0 \end{pmatrix} , \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} , \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} , \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} , \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} ,\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} ,\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} $
Sample 2
Input
1 1
Output
1
Sample 3
Input
1234 5678
Output
356279540
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tatyam
nok0