No.329 全射
shimomire問題文
$N$ 個の異なる集合 $A_1,\dots,A_N$ の要素数 $w_1,\dots,w_N$ (つまり、$w_i = |A_i|$ for $1 \le i \le N$ を満たす。)と
$1 \le i \le N$, $1 \le j \le N$ を満たすペア $(i,j)$ の集合 $E$ が与えられる。
関数 $f : A_i \to A_j$ が "生きている" ことを次で定義する。
- $i = j$ の時、$f$ は "生きている"。
- $(i,j) \in E$ の時、$f$ は "生きている"。
- $f : A_i \to A_j$, $g : A_j \to A_k$ が "生きている" 時、 $f$ と $g$ を合成した関数 $g \circ f$ は "生きている"。
- 1. 2. 3. から "生きている" と分かる関数に限り "生きている" 関数である。
ただし、全ての入力に対して同じ出力を返す関数は同じ関数であるとみなします。
（例えば、$A_1 = \{0\}$ の関数 $f : A_1 \to A_1$ と 関数 $f \circ f$ は全ての入力に対して同じ出力を返すため、同じ関数であるとみなします。）
また、集合 $A_1,\dots,A_N$ の各要素は全て異なるとします。
入力
$N$ $M$ $w_1$ $w_2$ $\dots$ $w_N$ $i_1$ $j_1$ $\vdots$ $i_M$ $j_M$
$N$($1 \le N \le 200$) は、与えられる集合の個数を表す。
$M$($0 \le M \le N^2$) は、ペアの集合 $E$ のサイズを表す。
$w_k$ ($1 \le k \le N$, $1 \le w_k \le 1000$) は、集合 $A_k$ の要素の個数を表す。
$i_k$, $j_k$ ($1 \le k \le M$, $1 \le i_k \le N$, $1 \le j_k \le N$) は、$E$ の要素の ペア $(i_k,j_k)$ を表す。
異なる $k$ の表すペア $(i_k,j_k)$ は全て異なる。
出力
"生きている" 関数のうち、全射の関数の個数を答えてください。 ただし、答えが非常に大きくなる場合があるため 1000000007($10^9+7$) で割った余りを出力してください。 最後に改行してください。
サンプル
サンプル1
入力
1 0 3
出力
6
仮に要素を {1,2,3} とすると、$\{1 \mapsto 1,2 \mapsto 2,3 \mapsto 3\}$,$\{1 \mapsto 1,2 \mapsto 3,3 \mapsto 2\}$,$\dots$ の 6 通りの全射が存在します。
サンプル2
入力
3 4 2 1 2 1 2 2 1 2 3 3 2
出力
7
$A_1 \to A_1$ の全射が $2$ 通り。
$A_1 \to A_2$ の全射が $1$ 通り。
$A_2 \to A_2$ の全射が $1$ 通り。
$A_3 \to A_3$ の全射が $2$ 通り。
$A_3 \to A_2$ の全射が $1$ 通り。
合計 $7$ 通りの全射が存在します。
$A_1 \to A_2$ と $A_2 \to A_3$ の関数を合成して出来る $A_1 \to A_3$ の関数は全射でないことに注意してください。
サンプル3
入力
4 3 1 2 3 4 4 2 2 3 3 1
出力
50
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。