Giải bài trực tuyến

Năm 2011, Việt Nam đề ra một kế hoạch phát triển đất nước. Bản kế hoạch sẽ gồm 2 giai đoạn: đầu năm và cuối năm. Ở mỗi giai đoạn, một số con đường nối giữa các cặp thành phố sẽ được xây dựng.

Bạn được cho một đồ thị thể hiện kết quả của kế hoạch, trong đó mỗi cạnh (i,j) thể hiện bản kế hoạch đã tạo ra một đường đi giữa thành phố i và thành phố j (không cần thiết phải là đường đi trực tiếp). Bạn cần đếm số lượng bản kế hoạch khác nhau có thể cho ra kết quả trên. Hai bản kế hoạch khác nhau nếu có một con đường được xây ở một giai đoạn của bản kế hoạch này nhưng không được xây ở giai đoạn tương ứng của bản kế hoạch kia.

Ví dụ, nếu giai đoạn đầu ta xây dựng đường nối (1,2), giai đoạn sau ta xây dựng đường nối (2,3) thì đồ thị kết quả sẽ có 3 cạnh: (1,2), (2,3), (1,3) do tồn tại đường đi giữa cả 3 thành phố này. Nếu ta xây (1,2) vào giai đoạn đầu và xây (1,2), (1,3) vào giai đoạn sau, ta thu được cùng một kết quả. Lưu ý, để tiết kiệm, ta chỉ có thể xây thêm một con đường nối một cặp thành phố trong một giai đoạn, nhưng giai đoạn sau ta có thể xây thêm một con đường nữa để thay thế do tốc độ lún sụt đường ở Việt Nam là khá nhanh.

Input

• Dòng đầu ghi số N thể hiện số thành phố. (1 <= N <= 7)

• N dòng sau, mỗi dòng ghi N số 0/1 thể hiện ma trận kề của đồ thị kết quả. Số 1 thể hiện giữa 2 thành phố tương ứng có đường đi. Đồ thị được cho luôn đúng đắn: nếu có đường đi giữa i và j thì sẽ có cạnh giữa i và j.

Output

• Một số duy nhất thể hiện số lượng bản kế hoạch khác nhau.

Example

Input:
2
0 1
1 0
Output:
3
Giải thích: Bạn có thể xây đường nối giữa 2 thành phố ở giai đoạn đầu, giai đoạn sau hoặc cả 2 giai đoạn.