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

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

5 секунд

64 мегабайти

Середня

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

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

$N = a_{n} \cdot F_{n} + a_{n - 1} \cdot F_{n - 1} + \dots + a_{1} \cdot F_{1}$ N = a_n \cdot F_n + a_{n-1} \cdot F_{n-1} + \ldots + a_1 \cdot F_1,

де $F_{k}$ F_k — це стандартна послідовність Фібоначчі, що визначається як $F_{0} = F_{1} = 1$ F_0 = F_1 = 1, $F_{i} = F_{i - 1} + F_{i - 2}$ F_i = F_{i-1} + F_{i-2}.

Наприклад, перші кілька натуральних чисел мають такі унікальні подання у системі Фібоначчі:

$1 = 1_{F}$ 1 = 1_F

$2 = 1 0_{F}$ 2 = 10_F

$3 = 10 0_{F}$ 3 = 100_F

$4 = 10 1_{F}$ 4 = 101_F

$5 = 100 0_{F}$ 5 = 1000_F

$6 = 100 1_{F}$ 6 = 1001_F

$7 = 101 0_{F}$ 7 = 1010_F

Джон записав дуже довгий рядок (вважайте його нескінченним), що складається з послідовних подань натуральних чисел у системі Фібоначчі. Наприклад, першими цифрами цього рядка є $110100101100010011010...$

Джону цікаво, скільки разів цифра $1$ зустрічається у $N$ -му префіксі цього рядка. Нагадаємо, що $N$ -ий префікс рядка — це рядок, який складається з його перших $N$ символів.

Напишіть програму, яка визначає, скільки разів цифра $1$ зустрічається у $N$ -му префіксі рядка Джона.

Вхідні дані

Вхід містить одне ціле число $N$ ( $0 \leq N \leq 1 0^{15}$ 0 \leq N \leq 10^{15}).

Вихідні дані

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

Приклади

Приклад 1