Cô giáo phát cho mỗi học sinh một tờ giấy kích thước 5 x 10 ô 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 S ô.

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: 2 cách tô gọi là khác nhau, nếu khi chồng khít 2 tờ giấy lên nhau (không xoay hoặc lật tờ giấy) có ít nhất một cặp 2 ô khác màu đè lên nhau. Còn số lượng thì cần phải tính cẩn thận. Đừng bao giờ trả lời sai với các em.

Yêu cầu: Cho S  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 S (0<S<=50),
• 5 dòng sau, mỗi dòng một xâu độ dài 10 chỉ gồm 2 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 là số lượng cách tô đạt điểm cao.