AT_jsc2021_g Spanning Tree

有一个包含 $N$ 个顶点的图 $G$，顶点编号为 $1, 2, \dots, N$。初始时，$G$ 中没有任何边。 接下来你可以向 $G$ 中添加若干无向边。但在所有边添加完毕后，对于任意的 $i, j\ (i \neq j)$，必须满足以下条件： - 当 $A_{i, j} = 1$ 时，顶点 $i$ 和顶点 $j$ 之间必须直接有一条边。 - 当 $A_{i, j} = 0$ 时，顶点 $i$ 和顶点 $j$ 之间不能直接有边。 - 当 $A_{i, j} = -1$ 时，是否有边都可以。 在所有可能的最终图 $G$ 中，有多少个是树？ 由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模后的结果。

输入通过标准输入给出，格式如下： > $N$ > $A_{1, 1}\ A_{1, 2}\ \cdots\ A_{1, N}$ > $\vdots$ > $A_{N, 1}\ A_{N, 2}\ \cdots\ A_{N, N}$

请输出答案对 $10^9 + 7$ 取模后的结果。

## 限制条件 - 所有输入均为整数。 - $2 \leq N \leq 300$ - $-1 \leq A_{i, j} = A_{j, i} \leq 1$ - $A_{i, i} = 0$ ## 样例解释 1 顶点 $1$ 和顶点 $2$ 之间必须有边，顶点 $1$ 和顶点 $4$ 之间、顶点 $3$ 和顶点 $4$ 之间不能有边。因此，满足条件的情况有以下 $2$ 种。  ## 样例解释 4 当区分顶点时，$11$ 个顶点的树一共有 $11^9$ 种。 由 ChatGPT 4.1 翻译