#881. COLOR - Tô màu

Cô giáo phát cho mỗi học sinh một tờ giấy kích thước ô vuông, trên tờ giấy có thể có một số ô đã được tô màu. Sau đó, cô yêu cầu học sinh làm các công việc sau:

• Có thể tô các ô nếu ô đó chưa được tô màu,
• Tiến hành tìm hình chữ nhật có diện tích lớn nhất chứa toàn các ô chưa được tô màu.

Những bài tô được điểm cao nếu sau khi tô (hoặc không tô) hình chữ nhật lớn nhất tìm được có đúng ô.

Là một người lâu năm trong nghề, cô giáo biết sớm hay muộn cũng sẽ có em hỏi là có bao nhiêu cách tô khác nhau để điểm cao và thế nào là hai cách tô khác nhau. Câu hỏi thứ hai không khó trả lời: hai cách tô gọi là khác nhau, nếu khi chồng khít hai tờ giấy lên nhau (không xoay hoặc lật tờ giấy) có ít nhất một cặp hai ô khác màu đè lên nhau. Còn số lượng thì cần phải tính cẩn thận.

Yêu cầu: Cho và màu của các ô đã được tô sẵn. Hãy xác định số cách tô được điểm cao.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên ;
• dòng sau, mỗi dòng một xâu độ dài chỉ gồm hai loại ký tự 0 hoặc 1 mô tả trạng thái tờ giấy, ký tự 0 – là ô chưa được tô, ký tự 1 là ô đã được tô màu.

Kết quả:

• Đưa ra một số nguyên - số lượng cách tô đạt điểm cao.

Ví dụ:

Dữ liệu:

4
1111111111
1111110011
0000010011
1111111111
1111111111

Kết quả:

61

Giới hạn:

• Có số test có đáp án không vượt quá .