/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点のグラフ G があり、頂点には 1, 2, \dots, N の番号がついています。はじめ、G には辺がありません。
これから G に何本か無向辺を追加します。ただし、辺を追加し終わった後、任意の i, j\,(i ≠ j) について以下の条件を満たす必要があります。
- A_{i, j} = 1 のとき、頂点 i と頂点 j を直接結ぶ辺が存在する。
- A_{i, j} = 0 のとき、頂点 i と頂点 j を直接結ぶ辺が存在しない。
- A_{i, j} = -1 のとき、どちらでもよい。
辺を追加し終わった後の G としてあり得るもののうち、木であるものはいくつあるでしょうか？
ただし、答えは非常に大きくなることがあるので、答えを (10^9 + 7) で割った余りを求めてください。
制約
- 入力は全て整数
- 2 ≤ N ≤ 300
- -1 ≤ A_{i, j} = A_{j, i} ≤ 1
- A_{i, i} = 0
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1, 1} \cdots A_{1, N}
\vdots
A_{N, 1} \cdots A_{N, N}
出力
答えを (10^9 + 7) で割った余りを出力せよ。
入力例 1
4 0 1 -1 0 1 0 -1 -1 -1 -1 0 0 0 -1 0 0
出力例 1
2
頂点 1 と頂点 2 の間には辺が必要で、頂点 1 と頂点 4 の間、頂点 3 と頂点 4 の間には辺を追加してはいけません。
したがって、以下の 2 個が条件を満たします。
入力例 2
3 0 1 1 1 0 1 1 1 0
出力例 2
0
入力例 3
3 0 0 0 0 0 0 0 0 0
出力例 3
0
入力例 4
11 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
出力例 4
357947677
頂点を区別するとき、11 頂点の木は全部で 11^9 個あります。
Score : 600 points
Problem Statement
We have a graph with N vertices numbered 1, 2, \dots, N. Initially, it has no edges.
Now, let us add some number of undirected edges to G so that the following condition holds for any i, j\,(i ≠ j) after addition.
- If A_{i, j} = 1, there is an edge directly connecting Vertex i and Vertex j;
- if A_{i, j} = 0, there is no edge directly connecting Vertex i and Vertex j;
- if A_{i, j} = -1, either is fine.
Among the graphs that can be G after addition, how many are trees?
Since the count can be enormous, find it modulo (10^9 + 7).
Constraints
- All values in input are integers.
- 2 ≤ N ≤ 300
- -1 ≤ A_{i, j} = A_{j, i} ≤ 1
- A_{i, i} = 0
Input
Input is given from Standard Input in the following format:
N
A_{1, 1} \cdots A_{1, N}
\vdots
A_{N, 1} \cdots A_{N, N}
Ouput
Print the count modulo (10^9 + 7).
Sample Input 1
4 0 1 -1 0 1 0 -1 -1 -1 -1 0 0 0 -1 0 0
Sample Output 1
2
We need an edge between Vertex 1 and Vertex 2, and we must not add an edge between Vertex 1 and Vertex 4 or between Vertex 3 and Vertex 4.
Thus, we have the following two valid graphs:
Sample Input 2
3 0 1 1 1 0 1 1 1 0
Sample Output 2
0
Sample Input 3
3 0 0 0 0 0 0 0 0 0
Sample Output 3
0
Sample Input 4
11 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
Sample Output 4
357947677
When we distinguish the vertices, there are 11^9 trees with 11 vertices.