eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Система Фібоначчі

Система Фібоначчі

Ліміт часу 5 секунд
Ліміт використання пам'яті 64 MiB

Маленький Джон вивчає числові системи. Після того, як він все вивчив про системи з фіксованою основою, Джона зацікавили інші, більш незвичні. Серед них він зустрів систему Фібоначчі, яка однозначно подає усі натуральні числа за допомогою двох цифр: одиниці та нуля. Але на відміну від звичної бінарної (двійкової) системи, у системі Фібоначчі не можна ставити дві единиці у сусідні позиції.

Можно довести, що якщо є число у системі Фібоначчі, то його значення дорівнює

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 (0N10^15).

Вихідні дані

Вивести одне число - кількість одиниць в N-ому префіксі рядка Джона.

Приклад

Вхідні дані #1
21
Вихідні дані #1
10
Автор Anton Maydell, Andrew Lopatin