問題一覧 > 通常問題

No.1846 Good Binary Matrix

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : 👑 potato167potato167 / テスター : nok0nok0 👑 tatyamtatyam
7 ProblemId : 6902 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。