G. Новый год и пути в двоичном дереве
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Новогоднее дерево является бесконечным полным двоичным деревом, корнем которого является вершина с номером 1. У каждой вершины v есть ровно два сына: вершина с номером (2·v) и вершина с номером (2·v + 1).

Полярные медведи очень любят украшать новогоднее дерево и Лимак конечно же не исключение. Поскольку он ещё только маленький медвежонок, ему разрешили украсить только некоторый простой путь между какой-то парой вершин. С другой стороны, ему разрешили самому выбрать какой именно путь украсить! Теперь он хочет знать количество неупорядоченных пар индексов (u, v) (u ≤ v), таких что сумма индексов на пути между u и v (включая крайние вершины) равняется s. Сможете ли вы помочь ему вычислить это количество?

Входные данные

В единственной строке входных данных записано целое число s (1 ≤ s ≤ 1015).

Выходные данные

Выведите одно целое число, равное количеству неупорядоченных пар индексов вершин, определяющих простой путь с суммой индексов равной s.

Пример
Входные данные
10
Выходные данные
4
Примечание

В примере из условия существует 4 пути с суммой индексов равной 10: