E. Количество k-хороших подотрезков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обозначим за $$$bit(x)$$$ количество единичных бит в двоичной записи неотрицательного целого числа $$$x$$$.

Назовем подотрезок массива $$$k$$$-хорошим, если он состоит только из чисел, в которых не более $$$k$$$ единичных бит, то есть подотрезок $$$(l, r)$$$ массива $$$a$$$ хороший, если для любого $$$i$$$, такого, что $$$l \le i \le r$$$ выполняется $$$bit(a_{i}) \le k$$$.

У вас есть массив $$$a$$$ длины $$$n$$$, состоящий из последовательных неотрицательных целых чисел начиная с $$$0$$$, то есть $$$a_{i} = i$$$ для $$$0 \le i \le n - 1$$$ (в $$$0$$$-индексации). Вам необходимо посчитать количество $$$k$$$-хороших подотрезков в этом массиве.

Поскольку ответ может быть очень большим, выведите его по модулю $$$10^{9} + 7$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$k$$$ ($$$1 \le n \le 10^{18}, 1 \le k \le 60$$$).

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

Для каждого набора входных данных в отдельной строке выведите одно целое число — количество $$$k$$$-хороших подотрезков по модулю $$$10^{9} + 7$$$.

Пример
Входные данные
10
6 1
16 2
1 1
3 1
31 3
14 1
1337 5
100000 20
795569939321040850 56
576460752303423268 59
Выходные данные
7
35
1
6
155
8
7323
49965
741136395
66679884
Примечание

Для первого набора входных данных $$$a = [0, 1, 2, 3, 4, 5]$$$, $$$k = 1$$$.

Чтобы найти ответ, давайте запишем все числа в двоичной записи:

$$$$$$a = [\color{green}{000}, \color{green}{001}, \color{green}{010}, \color{red}{011}, \color{green}{100}, \color{red}{101}]$$$$$$

Отсюда видно, что числа $$$3$$$ и $$$5$$$ имеют $$$2 \ge (k = 1)$$$ единичных бита в двоичной записи, поэтому в ответ должны войти все подотрезки, в которых нет ни $$$3$$$, ни $$$5$$$, это отрезки (в $$$0$$$-индексации): ($$$0$$$, $$$0$$$), ($$$0$$$, $$$1$$$), ($$$0$$$, $$$2$$$), ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$2$$$, $$$2$$$), ($$$4$$$, $$$4$$$).