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