Description

有 $N$ 个男人和 $N$ 个女人，都编号为 $1,2,…,N$。

对于每个 $i,j(1≤i,j≤N)$，男性 $i$ 和女性 $j$ 的可配队性以整数 $a_{i,j}$ 给出。如果 $a_{i,j}=1$，则男性 $i$ 和女性 $j$ 是可配对的；如果 $a_{i,j}=0$，则他们不可配对。

媒爷光头强正在尝试将这些男女配成 $N$ 对，在这里，每个男人和每个女人必须恰好属于一对。

找出光头强可以将他们配成 $N$ 对的方案数，模 $10^9+7$。

Input

输入格式如下：

$N\\a_{1,1} … a_{1,N}\\​ :\\a_{N,1} … a_{N,N}$

输入中的所有值都是整数。 $1≤N≤21\\a_{i,j}=0 or 1$.

Output

找出光头强可以将 $N$ 男 $N$ 女配成 $N$ 对的方案数，模 $10^9+7$。

Samples

3
0 1 1
1 0 1
1 1 1

3

有三种配对方式，如下：$(i,j)$ 表示一对男 $i$ 和女 $j$。

(1,2),(2,1),(3,3)

(1,2),(2,3),(3,1)

(1,3),(2,1),(3,2)

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

1

有一种配对方法，如下所示：

(1,2),(2,4),(3,1),(4,3)

1
0

0

21
0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1
0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0
0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1
0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1
0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0
1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0

102515160

务必输出模 $10^9+7$ 的结果。