Рассмотрим отрезок, на концах которого записаны единицы. Далее до бесконечности будем совершать следующую процедуру: для каждого отрезка, на концах которого записаны числа a и b (и внутри которого отсутствуют числа), запишем строго в его середине число a + b. То есть из начального отрезка
мы получим
Затем будут порождаться отрезки
и так далее до бесконечности. Сколько раз на этом отрезке будет записано натуральное число n?
Единственное число n (n ≤ 10^13
).
Вывести количество раз, которое число n встречается на отрезке.