NGÔN NGỮ MUMBA

Điểm: 10

Thời gian: 1.0s

Bộ nhớ: 1K

Tác giả:

Dạng bài

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 ≤ 10^5)\). 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

Output

Rang buộc