Bác Ba quản lý mạng lưới giao hàng nhanh trong huyện. Huyện có \(N\) bưu cục được đánh số từ \(0\) đến \(N-1\). Giữa mỗi cặp bưu cục có thể có hoặc không có một tuyến giao hàng một chiều; bác Ba thống kê được ma trận kề \(A\) trong đó \(A_{i,j} = 1\) nếu có tuyến đi từ \(i\) đến \(j\), ngược lại \(A_{i,j} = 0\). Bác Ba muốn biết có bao nhiêu hành trình xuất phát từ một bưu cục bất kỳ, đi theo các tuyến giao hàng có sẵn, sao cho mỗi bưu cục trong huyện được ghé đúng một lần (gọi là hành trình Hamilton). Hai hành trình khác nhau khi thứ tự các bưu cục ghé qua khác nhau.

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 15\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(N\) số nguyên \(0\) hoặc \(1\): \(A_{i,0}, A_{i,1}, \ldots, A_{i,N-1}\). Lưu ý \(A_{i,i} = 0\).

Định dạng đầu ra

• In ra một số nguyên duy nhất là số hành trình Hamilton khác nhau.

Ví dụ

Input:

3
0 1 1
1 0 1
1 1 0

Output:

6

Giải thích: Sáu hành trình: \((0,1,2)\), \((0,2,1)\), \((1,0,2)\), \((1,2,0)\), \((2,0,1)\), \((2,1,0)\).

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 8\).
• \(30\%\) số điểm ứng với \(N \le 12\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.