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_{i,j}\). Người đàn ông thứ \(i\) "hợp" với người phụ nữ thứ \(j\) nếu \(a_{i,j}=1\), ngược lại \(a_{i,j}=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_{i,1},a_{i,2},...,a_{i,N}(1\le i\le N,a_{i,j}\in \left\{0,1\right\})\)

Output

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

Example

3
0 1 1
1 0 1
1 1 1 

3