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

Всем известно, что Иллюминаты шифруют свои данные, используя ключ $$$2^x$$$, где $$$x$$$ – натуральное число. Умный подземный гриб Бретт считает, что пароль от зашифрованного архива данных Иллюминатов в точности совпадает с количеством способов взять XOR-сумму подмножества делителей ключа так, чтобы количество единиц в записи этой суммы в двоичной системе счисления было равно натуральному целому числу $$$y$$$. Помогите Бретту определить пароль от архива Иллюминатов, и выведите его по модулю $$$10^9+7$$$.

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

В одной строке даны два числа, $$$x$$$ и $$$y$$$, $$$1 \leqslant x, y \leqslant 2 \cdot 10^5$$$.

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

Выведите ответ на задачу по указанному модулю.

Система оценки

Группы в данной задаче «склеиваются». Это означает, что за подгруппу начисляются баллы, если хотя бы одна из ваших посылок успешно проходит все её тесты.

Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи
$$$0$$$ | $$$0$$$ | Тесты из условия | —
$$$1$$$ | $$$20$$$ | $$$x \leqslant 20$$$ | —
$$$2$$$ | $$$30$$$ | $$$x \leqslant 1000$$$ | 1
$$$3$$$ | $$$50$$$ | Нет дополнительных ограничений | 0, 1, 2

Примеры

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

    5 2

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

    15

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

    6 9

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

    0