**时间限制：** 1 秒 


**空间限制：** 512 MB

**相关文件：** 题目目录




## 题意简述

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

B君想知道有多少种不同的以$1$号点为根的生成树形图（在离散数学这门课程中，这个数据结构被叫做“根树”）。
由于答案可能很大，只需输出这个数除以$10007$所得的余数。

**L君的提示：**

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

**G君的提示：**

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

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

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

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

**R君的提示：**

如果你需要计算

$$
\left(a / b\right) \mod p 
$$

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

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

然后可以证明

$$
\left(a / b\right) \mod p = \left(a \mod p\right) \cdot c \mod p
$$

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

## 输入格式

从标准输入读入数据。

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

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

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

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

## 输出格式

输出到标准输出。

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






## 样例输入

```plain
4
0 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

```



## 样例输出

```plain
12

```


## 样例解释

矩阵$\mathbf{A}$为

$$
\left[
\begin{matrix}
 0&  0&  0&  0 \\
-1&  2& -1&  0 \\
-1& -1&  3& -1 \\
-1& -1& -1&  3
\end{matrix}
\right]
$$

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

$$
\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$。