Задача D. Сумма степеней двоек ≡

Условие

Тимофей выписал в ряд все степени двойки в порядке возрастания: 1, 2, 4, 8, 16, 32 и так далее. Потом его заинтересовал вопрос, возможно ли заданное число представить в виде суммы некоторых подряд идущих чисел этого ряда? Оказалось, что некоторые числа представить можно (например 14 = 2 + 4 + 8), а некоторые — нет (например 13). Помогите Тимофею найти количество чисел, не превосходящих n, которые можно представить подобным образом.

Формат входных данных

Первая строка входного файла содержит единственное натуральное число n.

Формат выходных данных

Выведите натуральное число — ответ на задачу.

Ограничения

1 ≤ n ≤ 10¹⁸

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 1000, получат не менее 30 баллов.

Решения, верно работающие при n ≤ 10⁵, получат не менее 60 баллов.

Пояснение к примеру

В примере дано n = 10. Существует всего три числа, не превосходящих 10, которые нельзя представить подобным образом, это 5, 9 и 10.

Примеры тестов

10

7