Вова на даче
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Всё шло своим чередом, пока лопата не лязгнула обо что-то твёрдое. Подкопав со всех сторон подозрительный объект, Вова вытащил на свет сундук с сокровищами. Всё было бы замечательно и прекрасно, если бы на сундуке не стоял замок. Чтобы замок открыть, требовалось ответить на вопрос «сколько чисел от $$$L$$$ до $$$R$$$ включительно имеют в битовом представлении без лидирующих нулей ровно $$$k$$$ нулевых битов?».

Вова в замешательстве: с одной стороны, хочется рассказать всем о находке, но с другой, надо бы решить загадку. Поколебавшись, Вова доверил решение задачи вам, а сам побежал рассказывать соседям радостную новость. Помогите Вове открыть сундук.

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

В единственной строке содержатся три целых числа $$$L$$$, $$$R$$$ и $$$k$$$ ($$$1 \le L \le R \le 10^{18}$$$, $$$0 \le k \le 60$$$) — границы рассматриваемого отрезка чисел и количество нулевых битов в записи.

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

Выведите единственное число — количество чисел от $$$L$$$ до $$$R$$$ включительно, в двоичной записи которых без лидирующих нулей ровно $$$k$$$ нулевых битов.

Пример

Входные данные
8 23 2
Выходные данные
6

Примечание

Двоичные записи чисел от 8 до 23: 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111. Жирным выделены числа с двумя нулями в битовой записи (двоичной системе счисления).