Система Фібоначчі
Маленький Джон вивчає числові системи. Після того, як він все вивчив про системи з фіксованою основою, Джона зацікавили інші, більш незвичні. Серед них він зустрів систему Фібоначчі, яка однозначно подає усі натуральні числа за допомогою двох цифр: одиниці та нуля. Але на відміну від звичної бінарної (двійкової) системи, у системі Фібоначчі не можна ставити дві единиці у сусідні позиції.
Можно довести, що якщо є число у системі Фібоначчі, то його значення дорівнює
N = a_n·F_n + a_{n-1}·F_{n-1} + ... + a_1·F_1,
де F_k - послідовність Фібоначчі, яка задається співвідношеннями F_0 = F_1 = 1, F_i = F_{i-1} + F_{i-2}.
Наприклад, перші декілька натуральних чисел мають наступні подання у системі Фібоначчі:
1 = 1_F
2 = 10_F
3=100_F
4=101_F
5=1000_F
6=1001_F
7=1010_F
Джон записав дуже довгий рядок (вважайте що нескінченний), який складаєьбмя з поданння послідовних натуральних чисел у системі Фібоначчі. Наприклад, першими цифрами такого рядка будуть 110100101100010011010...
Джона цікавить, скільки разів зустрічається цифра 1 у N-ому префіксі рядка. Нагадаємо, що N-им префіксом рядка називається рядок, який складається з його перших N символів.
Напишіть програму, яка підрахує кількість цифр 1, які зустрічаються у N-ому префіксі рядка Джона.
Вхідні дані
Одне ціле число N (0 ≤ N ≤ 10^15).
Вихідні дані
Вивести одне число - кількість одиниць в N-ому префіксі рядка Джона.