Новогоднее дерево является бесконечным полным двоичным деревом, корнем которого является вершина с номером 1. У каждой вершины v есть ровно два сына: вершина с номером (2·v) и вершина с номером (2·v + 1).
Полярные медведи очень любят украшать новогоднее дерево и Лимак конечно же не исключение. Поскольку он ещё только маленький медвежонок, ему разрешили украсить только некоторый простой путь между какой-то парой вершин. С другой стороны, ему разрешили самому выбрать какой именно путь украсить! Теперь он хочет знать количество неупорядоченных пар индексов (u, v) (u ≤ v), таких что сумма индексов на пути между u и v (включая крайние вершины) равняется s. Сможете ли вы помочь ему вычислить это количество?
Выходные данные
Выведите одно целое число, равное количеству неупорядоченных пар индексов вершин, определяющих простой путь с суммой индексов равной s.
Примечание
В примере из условия существует 4 пути с суммой индексов равной 10:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
|
4
|