题目描述

很遗憾，出题人想不出一个有趣的故事，因此他只是请求你解决以下问题。

给定由 $n$ 个正整数组成的数组 $a$，计算按位与后的二进制表示中恰好 $k$ 位为 1 的非空子序列数量。答案可能很大，因此输出时对 $10^9+7$ 取模。

回顾一下数组 $a$ 的子序列是从 $a$ 中去掉一些（可能为零）元素得到的序列。例如，$[1,2,3]$，$[3]$，$[1,3]$ 是 $[1,2,3]$ 的子序列，但 $[3,2]$ 和 $[4,5,6]$ 不是。

请注意 AND 表示按位与操作。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t(1≤t≤10^4)$。以下是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k(1≤n≤2×10^5，0≤k≤6)$ ——数组的长度和应在其二进制表示中具有的按位 AND 值中的设置位数。

每个测试用例的第二行包含 $n$ 个整数 $a_i(0≤a_i≤63)$ ——数组 $a$。

保证所有测试用例中 $n$ 的总和不超过 $2×10^5$。

输出格式

对于每个测试用例，输出一个整数——在其按位 AND 后的二进制表示中恰好有 $k$ 位为 1 的子序列数量。答案可能很大，因此输出时对 $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

样例说明