Có $N$ học sinh nam và $N$ học sinh nữ đều được đánh số $1,2,3...N$.

Với mỗi cặp số $i,j$ $(1\le i,j\le N)$, độ hợp nhau của học sinh nam $i$ và học sinh nữ $j$ là $a_{i,j}$. Nếu $a_{i,j}=1$ thì bạn nam $i$ và bạn nữ $j$ hợp nhau, nếu $a_{i,j}=0$ thì ngược lại.

Huy tìm cách chia $N$ học sinh nam và $N$ học sinh nữ thì $N$ cặp, trong đó mỗi cặp gồm một nam và một nữ hợp nhau.

Hãy tìm số cách khác nhau mà Huy có thể chia, modulo ${10}^9+7$

Input

• Dòng đầu tiên gồm $N$ $(1\le N\le 21)$
• $N$ dòng sau, mỗi dòng gồm $N$ số nguyên $0$ hoặc $1$. Trong đó số thứ $j$ ở hàng thứ $i$ là giá trị $a_{i,j}$

Output

• In ra số cách chia cặp thỏa mãn, modulo ${10}^9+7$

Input 1

3
0 1 1
1 0 1
1 1 1

Output 1

3

Giải thích 1

Có $3$ cách chia thỏa mãn như sau $(i,j)$ ký hiệu cho cặp nam $i$ và nữ $j$

• (1,2); (2,1); (3,3)
• (1,2); (2,3); (3,1)
• (1,3); (2,1); (3,2)

Input 2

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

Output 2

1

Giải thích 2

Có 1 cách thỏa mãn: (1,2); (2,4); (3,1); (4,3)

Input 3

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

Output 3

102515160