問題一覧 > 通常問題

No.1846 Good Binary Matrix

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 85
作問者 : 👑 potato167 / テスター : tatyam nok0
お気に入りにしたユーザー ProblemId : 6902 / 自分の提出
問題文最終更新日: 2025-05-02 17:45:19
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 332 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。