Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

V11PLAN - Kế hoạch phát triể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.

Được gửi lên bởi:VOJ Team
Ngày:2011-01-03
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VNOI Online 2011
Tác giả: Khúc Anh Tuấn

hide comments
2013-11-20 13:08:51 up!
khó hiểu vl.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.