Hồ được biểu diễn bởi ma trận \(n\times m\): 0 là nước và 1 là lá sen. Từ một lá sen, ếch Maša có thể nhảy tới bất kỳ lá sen khác nào cùng hàng hoặc cùng cột. Nếu lần nhảy trước thay đổi cột, lần nhảy kế tiếp phải thay đổi hàng; nếu lần nhảy trước thay đổi hàng, lần nhảy kế tiếp phải thay đổi cột. Ngay sau khi Maša rời một lá sen, lá đó chìm và không thể được dùng lại. Maša được chọn tùy ý lá sen đầu tiên và phải đi qua đúng \(5\) lá sen, kể cả lá bắt đầu. Hãy đếm số đường đi có thể. Hai đường đi là khác nhau nếu vị trí của ít nhất một trong năm lá sen trên đường đi khác nhau.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,m\) (\(1\le n,m\le2000\)). \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) ký tự 0 hoặc 1, mô tả các ô của hồ.

Dữ liệu ra

In một số nguyên: số đường đi hợp lệ.

Ràng buộc

Các giới hạn chính thức được nêu trong phần Dữ liệu vào.

Phân nhóm

1. \(8\) điểm: \(n,m\le4\).
2. \(27\) điểm: \(n,m\le10\).
3. \(58\) điểm: \(n,m\le400\).
4. \(17\) điểm: không có ràng buộc thêm.

Ví dụ

2 3
111
110

4

4 4
1111
1111
1111
1111

2304

2 5
11110
01111

48

Nguồn

COCI 2025/2026 - Vòng 5, bài Pet.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.