Có ~N~ người đàn ông và ~N~ người phụ nữ, được đánh số ~(1,2,3,...,N)~

Với mỗi ~i,j(1\le i,j\le N)~, độ "hợp nhau" của người đàn ông thứ ~i~ và người phụ nữ thứ ~j~ được kí hiệu bởi ~a_{ij}~. Người đàn ông thứ ~i~ "hợp" với người phụ nữ thứ ~j~ nếu ~a_{ij}=1~, ngược lại ~a_{ij}=0~.

~Kaninho~ muốn tạo ra ~N~ cặp "hợp nhau". Trong đó, mỗi người đàn ông và mỗi người phụ nữ phải thuộc về chính xác một cặp.

Tìm số cách mà Kaninho có thể tạo ra ~N~ cặp hợp nhau, vì đáp án có thể lớn, nên cần phải lấy mod ~10^9+7~ trước khi in ra.

Input

• Dòng thứ nhất chứa số nguyên ~N(1\le N\le 21)~
• ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên ~a_{i1}, a_{i2}, ..., a_{i,N}; (1 \le i \le N, a_{ij} \in \left\{0,1\right\})~

Output

• In ra giá trị cần tìm.

Sample

Input #1

3
0 1 1
1 0 1
1 1 1

Output #1

3

Input #2

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

Output #2

1

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

Hint

Sample test 1:

~3~ cách thỏa mãn yêu cầu bài toán đó là:

• ~(1,2),(2,1),(3,3)~
• ~(1,2),(2,3),(3,1)~
• ~(1,3),(2,1),(3,2)~

Sample test 2:

~1~ cách thoả mãn yêu cầu bài toán là:~(1,2),(2,4),(3,1),(4,3)~

Problem source: DP Contest Atcoder