There are $N$ men and $N$ women, both numbered $1,2,\dots ,N$.

For each $i,j$ $(1\le i,j\le N)$, the compatibility of Man $i$ and Woman $j$ is given as an integer $a_{i,j}$. If $a_{i,j}=1$, Man $i$ and Woman $j$ are compatible; if $a_{i,j}=0$, they are not.

Taro is trying to make $N$ pairs, each consisting of a man and a woman who are compatible. Here, each man and each woman must belong to exactly one pair.

Find the number of ways in which Taro can make $N$ pairs, modulo ${10}^9+7$.

Constraints

• All values in input are integers.
• $1\le N\le 21$
• $a_{i,j}$ is $0$ or $1$.

Input Specification

The first line will contain the integer $N$.

The next $N$ lines will each contain $N$ integers, $a_{i,j}$.

Output Specification

Print the number of ways in which Taro can make $N$ pairs, modulo ${10}^9+7$.

Sample Input 1

3
0 1 1
1 0 1
1 1 1

Sample Output 1

3

Explanation For Sample 1

There are three ways to make pairs, as follows ($(i,j)$ denotes a pair of Man $i$ and Woman $j$):

• $(1,2),(2,1),(3,3)$
• $(1,2),(2,3),(3,1)$
• $(1,3),(2,1),(3,2)$

Sample Input 2

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

Sample Output 2

1

Explanation For Sample 2

There is one way to make pairs, as follows:

• $(1,2),(2,4),(3,1),(4,3)$

Sample Input 3

1
0

Sample Output 3

0

Sample Input 4

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

Sample Output 4

102515160

Explanation For Sample 4

Be sure to print the number modulo ${10}^9+7$.