310414: CF1829H. Don't Blame Me

H. Don't Blame Metime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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$.

ExampleInput

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

Output

31
10
10
1
4032
15

题目大意：
给定一个由n个正整数组成的数组a，计算有多少个非空子序列，使得这些子序列中元素的按位AND结果在二进制表示中恰好有k个置位的比特。答案可能很大，所以结果要对10^9+7取模。

输入输出数据格式：
输入：
- 第一行包含一个整数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。

输出：
- 对于每个测试用例，输出一个整数，表示满足条件的子序列数量，结果对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
```题目大意： 给定一个由n个正整数组成的数组a，计算有多少个非空子序列，使得这些子序列中元素的按位AND结果在二进制表示中恰好有k个置位的比特。答案可能很大，所以结果要对10^9+7取模。 输入输出数据格式： 输入： - 第一行包含一个整数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。 输出： - 对于每个测试用例，输出一个整数，表示满足条件的子序列数量，结果对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 ```