CF1829H Don't Blame Me

很遗憾，出题人没能想出有趣的故事，因此他直接让你解决如下问题。 给定一个由 $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}$ 表示[按位与运算](https://en.wikipedia.org/wiki/Bitwise_operation#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$ 取模后的结果。

由 ChatGPT 4.1 翻译