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

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

Taro tìm cách chia ~N~ người đàn ông và ~N~ người phụ nữ thành ~N~ cặp, trong đó mỗi cặp gồm một người đàn ông và một người phụ nữ hợp nhau.

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

Input

Dòng đầu tiên gồm số ~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ị của ~a_{i,j}~.

Output

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

Sample 1

Input

3
0 1 1
1 0 1
1 1 1

Output

3

Có 3 cách thỏa mãn như sau (~(i,j)~ ký hiệu cho cặp giữa ông ~i~ và bà ~j~)

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

Sample 2

Input

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

Output

1

Có 1 cách thỏa mãn như sau

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

Sample 3

Input

1
0

Output

0

Sample 4

Input

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

102515160

Lưu ý kết quả cần phải được in ra theo modulo ~10^9+7~.