Mỗi từ trong ngôn ngữ của bộ tộc Mumba hình thành từ các ký tự a và b theo quy tắc sau:
- Không chứa 2 ký tự b liên tiếp,
- Không có ba từ con giống nhau đứng liên tiếp trong một từ, như vậy aaa không phải là một từ (có 3 từ con a liên tiếp), aabababa cũng không phải là một từ (có 3 từ con ab liên tiếp).
Tất cả các xâu thỏa mãn những điều kiện trên đều là từ trong ngôn ngữ Mumba.
Yêu cầu: Cho số nguyên k(1≤k≤105). Hãy xác định số từ trong ngôn ngữ Mumba có độ dài đúng bằng k.
Dữ liệu: Gồm một dòng chứa số nguyên k.
Kết quả: Một số nguyên – kết quả tìm được.
Ví dụ:
Input
Copy
5
Output
Copy
7
Ràng buộc
- 30% số test ứng 30% số điểm có k≤20
- 60% số test ứng 60% số điểm có k≤25