CF1829H.Don't Blame Me

Sadly, the problem setter couldn't think of an interesting story, thus he just asks you to solve the following problem.

Given an array $a$ consisting of $n$ positive integers, count the number of non-empty subsequences for which the bitwise $\mathsf{AND}$ of the elements in the subsequence has exactly $k$ set bits in its binary representation. The answer may be large, so output it modulo $10^9+7$.

Recall that the subsequence of an array $a$ is a sequence that can be obtained from $a$ by removing some (possibly, zero) elements. For example, $[1, 2, 3]$, $[3]$, $[1, 3]$ are subsequences of $[1, 2, 3]$, but $[3, 2]$ and $[4, 5, 6]$ are not.

Note that $\mathsf{AND}$ represents the bitwise AND operation.

遗憾的是，出题人未能构思出一个有趣的故事，因此他直接要求你解决以下问题。

给定一个由 $n$ 个正整数组成的数组 $a$，请计算满足如下条件的非空子序列的个数：该子序列中所有元素的按位与（$\mathsf{AND}$）结果在二进制表示中恰好含有 $k$ 个 1（即恰好有 $k$ 个置位）。答案可能很大，请对 $10^9+7$ 取模输出。

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

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

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case consists of two integers $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$, $0 \le k \le 6$) — the length of the array and the number of set bits that the bitwise $\mathsf{AND}$ the counted subsequences should have in their binary representation.

The second line of each test case consists of $n$ integers $a_i$ ($0 \leq a_i \leq 63$) — the array $a$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5$，$0 \le k \le 6$）——分别表示数组长度，以及所统计子序列的按位 $\mathsf{AND}$ 结果在二进制表示中应具有的置位比特（set bits）数量。

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

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

For each test case, output a single integer — the number of subsequences that have exactly $k$ set bits in their bitwise $\mathsf{AND}$ value's binary representation. The answer may be large, so output it modulo $10^9+7$.

对于每个测试用例，输出一个整数——即其按位与（$\mathsf{AND}$）结果的二进制表示中恰好含有 $k$ 个比特位为 1 的子序列个数。答案可能很大，请对 $10^9+7$ 取模后输出。