Cho một bảng lưới hình chữ nhật kích thước . Nhiệm vụ của bạn là tính số cách lát kín hoàn toàn bảng này bằng các mảnh ghép đơn vị dựa trên các quy tắc sau:
Nếu là một số nguyên lẻ, không có phương án nào để lát kín bảng (số cách bằng ).
Nếu là một số nguyên chẵn (), bảng có thể được chia thành khối độc lập kích thước . Mỗi khối có chính xác cách lát khác nhau.
Tổng số cách lát bảng là tích số cách lát của các khối độc lập đó.
Nói cách khác, gọi là số cách lát bảng , ta có hệ thức:
nếu .
nếu ().
.
Dữ liệu:
Một dòng duy nhất chứa số nguyên ().
Kết quả:
Một số nguyên duy nhất là số lượng cách lát kín bảng .
Ví dụ:
Dữ liệu:
4
Kết quả:
4
Giải thích:
Vì là số chẵn, ta có .
Dữ liệu:
3
Kết quả:
0
Giải thích:
Với là số lẻ, theo quy tắc số cách lát luôn bằng .
Giới hạn:
Subtask #1 (20% số điểm): .
Subtask #2 (20% số điểm): luôn là số nguyên lẻ ().
Subtask #3 (60% số điểm): , không có ràng buộc gì thêm.
