Đang là mùa hè oi bức, Phú ông rất muốn đổi lấy cái quạt mo của Bờm nên đưa ra đủ các điều kiện mà chàng Bờm vẫn chưa ưng, biết được Bờm chưa có đất làm nhà nên Phú ông quyết định đổi một mảnh đất của mình cho Bờm làm nhà để lấy cái quạt mo của Bờm, tất nhiên là chàng Bờm đồng ý ngay.
Phú Ông có một mảnh đất hình chữ nhật được chia thành M hàng N cột, mỗi ô nằm trên giao của một hàng và một cột ta gọi là một ô đơn vị. Phú Ông muốn đổi cho Bờm một mảnh đất hình vuông chứa chọn vẹn các ô đơn vị này để lấy quạt mo của Bờm. Trên mảnh đất của Phú Ông có những ô là đất bằng nhưng cũng có những ô chứa những ụ đá mà nếu trong mảnh đất hình vuông mà Bờm chọn có chứa ụ đá thì Bờm sẽ không thể làm nhà được. Bờm đang lúng túng không biết mình có bao nhiêu cách chọn mảnh đất hình vuông khác nhau mà trên đó không có ụ đá nào. Em hãy lập chương trình giúp Bờm đếm số cách chọn nhé.
Dữ liệu vào: Nhập từ tệp văn bản test.inp có cấu trúc như sau:
Dữ liệu ra: Ghi ra file văn bản test.out một số nguyên duy nhất là số cách chọn mảnh đất hình vuông của Bờm.
| # | test.inp | test.out |
|---|---|---|
| 1 |