No.1846 Good Binary Matrix
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : 👑
potato167
/ テスター :
tatyam
nok0
タグ : / 解いたユーザー数 80
作問者 : 👑
potato167
/ テスター :
tatyam
nok0
問題文最終更新日: 2022-03-18 23:32:21
問題文
整数 $H,W$ が与えられます。以下の条件を満たす $H \times W$ 行列 $A$ をいい行列とします。
- 行列の任意の要素は $0$ か $1$ である。
- 全ての要素が $0$ であるような行や列が存在しない。つまり、
- 任意の $1\leq i\leq H$ について、 $A_{i,j}=1$ となる $1\leq j \leq W$ が存在する。
- 任意の $1\leq j \leq W$ について、 $A_{i,j}=1$ となる $1\leq i \leq H$ が存在する。
いい行列として考えられる行列 $A$ の場合の数を求めてください。 ただし、答えは非常に大きくなることがあるので $(10^{9}+7)$ で割ったあまりを出力してください。
制約
- $1\leq H,W \leq 10^{6}$
- 入力は全て整数
入力
$H \; W$
出力
答えを $(10^{9}+7)$ で割ったあまりを出力してください。 最後に改行してください。
サンプル
サンプル1
入力
2 2
出力
7
以下の $7$ つがいい行列です。 $ 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} $
サンプル2
入力
1 1
出力
1
サンプル3
入力
1234 5678
出力
356279540
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。