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

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