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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 1018

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
10
7

0.082s 0.019s 13