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~.