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 đề 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.
Input
Một dòng chứa số nguyên k.
Output
Một số nguyên – kết quả tìm được.
Input
5
Output
7
Nguồn: 3D '1819