分数: 600 点
问题陈述
我们有一个图表 N 顶点编号 1, 2, \dots, N。最初,它没有边缘。
现在,让我们添加一些无向边 G 因此以下条件适用于任何
添加后的 i, j\,(i ≠ j) 。
- If A_{i, j} = 1,有一条边直接连接Vertex i 和顶点 j;
- if A_{i, j} = 0,没有直接连接Vertex的边 i 和顶点 j;
- if 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,并且我们不能在 Vertex 之间添加边 1 和顶点 4 或顶点之间 3 和顶点 4.
因此,我们有以下两个有效的图表:

示例输入 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^9 树木 11 顶点。