MUMBA - Ngôn ngữ Mumba
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Mỗi từ trong ngôn ngữ của bộ tộc Mumba hình thành từ các ký tự ab 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.

Ví dụ

Input

5

Output

7


Nguồn: 3D '1819

Back to Top