题目描述

很遗憾，出题人没能想出有趣的故事，因此他直接让你解决如下问题。

给定一个由 $n$ 个正整数组成的数组 $a$，请你统计有多少个非空子序列，其所有元素的按位 $\mathsf{AND}$ 运算结果的二进制表示中恰好有 $k$ 个 $1$。由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

回忆一下，数组 $a$ 的子序列是可以通过删除一些（可能为零个）元素从 $a$ 得到的序列。例如，$[1, 2, 3]$、$[3]$、$[1, 3]$ 都是 $[1, 2, 3]$ 的子序列，但 $[3, 2]$ 和 $[4, 5, 6]$ 不是。

注意，$\mathsf{AND}$ 表示按位与运算。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \times 10^5$，$0 \le k \le 6$），分别表示数组的长度和要求按位 $\mathsf{AND}$ 结果中 $1$ 的个数。

每组测试用例的第二行包含 $n$ 个整数 $a_i$（$0 \leq a_i \leq 63$），表示数组 $a$。

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

输出格式

对于每组测试用例，输出一个整数，表示满足条件的子序列数量。由于答案可能很大，请输出对 $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

样例说明

由 ChatGPT 4.1 翻译

来源

Codeforces 1829H，英文题名 Don't Blame Me。