时间限制： 1.0 秒

空间限制： 512 MB

题目描述

B 君有一个 $n$ 个点的有向图。

B 君想知道有多少种不同的以 $1$ 号点为根的生成树形图（在离散数学这门课程中，这个数据结构被叫做“根树”）。

由于答案可能很大，只需输出这个数除以 $10007$ 所得的余数。

L 君的提示：

以 $1$ 号点为根的树形图，就是说，从有向图中选出 $n−1$ 条边，构成一个树，这个树的根节点是 $1$，对于所有其他点 $i$，存在且只存在一条从 $i$ 到 $1$ 的有向路径。

G 君的提示：

对于一个有向图，我们构造如下 $A$ 矩阵（其中 $a_{i,j}$ 表示矩阵第 $i$ 行第 $j$ 列的元素）：

对于 $i \neq j$，$a_{i,j}$ 为 $i$ 到 $j$ 的边数的相反数。

$a_{i,i}$ 为 $i$ 的出度。

那么这个矩阵删去第 $1$ 行第 $1$ 列之后的余子式为以 $1$ 号点为根的树形图的数量。

R 君的提示：

如果你需要计算

$$(a/b) \bmod p$$

其中 $p$ 是质数，$b$ 是 $a$ 的约数，$b$ 与 $p$ 互质。

你可以先找到 $c$，满足 $bc \bmod p = 1$。

然后可以证明

$$(a/b) \bmod p=(a \bmod p) \cdot c \bmod p$$

其中满足 $b\cdot c \bmod p = 1$ 的 $c$，被称为 $b$ 的乘法逆元，满足这个条件的 $c$ 存在且唯一。

输入格式

从标准输入读入数据。

输入第一行一个正整数 $n$，表示一共有 $n$ 个点。

以下 $n$ 行，每行 $n$ 个数，表示这个有向图的邻接矩阵。

其中如果第 $i$ 行第 $j$ 个数是 $1$，表示 $i$ 到 $j$ 存在一条有向边，如果是 $0$，表示不存在有向边。

在本题中没有重边和自环，所以这个矩阵是 $01$ 矩阵，主对角线上的数均为 $0$。

输出格式

输出到标准输出。

一行一个整数，表示答案。

4
0 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

12

样例 1 解释

矩阵 $A$ 为

$$\begin{bmatrix} 0 & 0 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{bmatrix}$$

删掉第一行第一列之后的，做行列式求值（也就是余子式）为

$$\left| \begin{matrix} 2 & -1 & 0 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{matrix} \right| = 12$$

子任务

对于 $10\%$ 的数据 $n \le 3$；

对于 $20\%$ 的数据 $n \le 4$；

对于 $40\%$ 的数据 $n \le 10$；

对于 $60\%$ 的数据 $n \le 16$；

对于 $100\%$ 的数据 $n \le 100$。