Tô bảng đẹp
Đề bài
Mô tả
Cho một bảng vuông ô. Mỗi ô được tô bằng một trong hai màu: trắng hoặc đen.
Một cách tô được gọi là đẹp nếu với mọi hai hàng kề nhau, hoặc hai hàng đó hoàn toàn giống nhau ở mọi cột, hoặc hoàn toàn khác nhau ở mọi cột. Điều kiện tương tự cũng được áp dụng cho mọi hai cột kề nhau.
Một cách tô được gọi là hợp lệ nếu nó đẹp và không tồn tại bất kỳ hình chữ nhật con đơn sắc (gồm các ô liên tiếp cùng màu, các cạnh song song với cạnh bảng) nào có diện tích lớn hơn hoặc bằng ô.
Hãy đếm số cách tô hợp lệ của bảng đã cho. Vì kết quả có thể rất lớn, in ra phần dư của nó khi chia cho .
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và — kích thước bảng và giới hạn diện tích hình chữ nhật đơn sắc.
Dữ liệu ra
In ra một số nguyên duy nhất là số cách tô hợp lệ modulo .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 | 6 | Trong tổng số cách tô đẹp của bảng , có cách mà mọi hình chữ nhật đơn sắc đều có diện tích nhỏ hơn . Hai cách bị loại là hai cách tô tất cả ô cùng màu. |
| 1 1 | 0 | Bảng luôn chứa một hình chữ nhật đơn sắc ô, không thoả mãn diện tích nhỏ hơn . |
| 49 1808 | 359087121 | Kết quả lấy modulo . |
Bình luận