H. Не вините меня
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

К сожалению, автор задачи не смог придумать интересную историю, поэтому он просто просит вас решить следующую задачу.

Дан массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел. Посчитайте количество подпоследовательностей, для которых побитовое $$$\mathsf{AND}$$$ элементов в подпоследовательности имеет ровно $$$k$$$ единичных битов в двоичном представлении. Ответ может быть большим, поэтому выведите его по модулю $$$10^9+7$$$.

Напомним, что подпоследовательность массива $$$a$$$ - это последовательность, которую можно получить из $$$a$$$, удалив некоторые (возможно, ни одного) элементы. Например, $$$[1, 2, 3]$$$, $$$[3]$$$, $$$[1, 3]$$$ являются подпоследовательностями $$$[1, 2, 3]$$$, но $$$[3, 2]$$$ и $$$[4, 5, 6]$$$ - нет.

Обратите внимание, что $$$\mathsf{AND}$$$ обозначает логическую операцию AND.

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

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

Первая строка каждого тестового случая состоит из двух целых чисел $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \le k \le 6$$$) — длина массива и количество единичных битов, которое должно быть у побитового $$$\mathsf{AND}$$$ подсчитанных подпоследовательностей в двоичном представлении.

Вторая строка каждого тестового случая состоит из $$$n$$$ целых чисел $$$a_i$$$ ($$$0 \leq a_i \leq 63$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превышает $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
6
5 1
1 1 1 1 1
4 0
0 1 2 3
5 1
5 5 7 4 2
1 2
3
12 0
0 2 0 2 0 2 0 2 0 2 0 2
10 6
63 0 63 5 5 63 63 4 12 13
Выходные данные
31
10
10
1
4032
15