Lát hành lang
Đề bài
Mô tả
Trong cuộc thi Sáng tạo Hoa văn Trong nhà (ICPC) năm nay, các đội cần trang trí một hành lang dài. Sàn hành lang có dạng hình chữ nhật, có thể xem như một lưới gồm ô.
Thông thường, người ta dùng các viên gạch hoặc để lát sàn. Tuy nhiên, để đảm bảo tính sáng tạo của cuộc thi, ban giám khảo ICPC yêu cầu mọi đội phải dùng gạch hình chữ L. Gạch hình chữ L là viên gạch nằm gọn trong một lưới và phủ đúng trong ô của lưới đó; có hình dạng, tương ứng với ô bị bỏ trống là ô trên trái, trên phải, dưới trái hoặc dưới phải:
## ## #. .#
#. .# ## ##
Mỗi đội có thể dùng một số viên gạch chữ L để lát hành lang. Một đội có thể chọn không dùng viên gạch nào nếu cho rằng hành lang đã đủ đẹp và không cần trang trí thêm. Mọi đội phải đặt gạch lên sàn sao cho:
- Mỗi viên gạch chữ L phủ đúng ba ô trên sàn.
- Không có ô nào trên sàn bị phủ bởi nhiều hơn một viên gạch.
Định nghĩa độ phủ của một hành lang đã lát là số ô được phủ trong hành lang. Ban giám khảo ICPC muốn đưa ra một số dự đoán trước cuộc thi, vì vậy họ muốn biết tổng độ phủ của tất cả các cách lát hành lang.
Hai cách lát hành lang được coi là khác nhau khi và chỉ khi ít nhất một trong hai điều sau đúng:
- Có một ô được phủ trong cách lát này nhưng không được phủ trong cách lát kia.
- Có một cặp ô được phủ bởi cùng một viên gạch chữ L trong cách lát này, nhưng bởi hai viên gạch khác nhau trong cách lát kia.
Cho là số cột của sàn hành lang. Hãy tính tổng độ phủ của tất cả các cách lát hành lang, lấy phần dư khi chia cho .
Dữ liệu vào
Một dòng duy nhất chứa số nguyên (), số cột của sàn hành lang.
Dữ liệu ra
In ra tổng độ phủ của tất cả các cách lát hành lang, lấy phần dư khi chia cho .
Ràng buộc
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 | 12 | Sàn có kích thước : có cách lát với độ phủ (không dùng gạch) và cách lát với độ phủ (dùng một viên gạch, có hình dạng). Tổng độ phủ là . |
| 3 | 36 | Sàn có kích thước : có cách lát với độ phủ , cách lát với độ phủ và cách lát với độ phủ . Tổng độ phủ là . |
| 177013 | 912417795 |
Bình luận