Tháp Đỏ-Xanh
Đề bài
Mô tả
Bạn có khối màu đỏ và khối màu xanh để xây một tòa tháp đỏ-xanh theo các quy tắc sau:
- Tháp gồm một số tầng.
- Nếu tháp có tầng thì tầng thứ nhất gồm khối, tầng thứ hai gồm khối, ..., tầng cuối cùng gồm đúng khối. Nói cách khác, mỗi tầng có ít hơn tầng ngay trên nó (tính từ dưới lên) đúng một khối.
- Mỗi tầng chỉ được dùng các khối cùng một màu.
Gọi là số tầng lớn nhất có thể của một tòa tháp xây được từ khối đỏ và khối xanh thỏa các quy tắc trên. Nhiệm vụ của bạn là đếm số tòa tháp khác nhau có đúng tầng có thể xây được.
Hai tòa tháp được coi là khác nhau nếu tồn tại một tầng mà ở tháp này gồm các khối đỏ còn ở tháp kia gồm các khối xanh.
Hãy in ra số tòa tháp khác nhau có đúng tầng theo modulo .
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và — số khối đỏ và số khối xanh.
Dữ liệu ra
In ra một số nguyên duy nhất — số tòa tháp khác nhau có đúng tầng, theo modulo .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 6 | 2 | Số tầng tối đa là (cần khối, vừa đủ ). Tầng cỡ 4 phải là xanh (chỉ có 4 đỏ). Phần còn lại cần tô màu cho các tầng sao cho dùng đúng 4 đỏ: hoặc tầng cỡ 4... thực chất có đúng 2 cách hợp lệ. |
| 9 7 | 6 | Số tầng tối đa (cần khối, có ). Có cách phân màu hợp lệ. |
| 1 1 | 2 | : tháp một tầng cỡ 1, có thể là đỏ hoặc xanh, tổng cộng cách. |
Bình luận