别怪我

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个由 $n$ 个非负整数组成的数组 $a$。请统计有多少个非空子序列，使其所有元素的按位与结果的二进制表示中恰好有 $k$ 个 $1$。

答案对 $10^9+7$ 取模。

输入格式

第一行包含整数 $t$（$1\le t\le10^4$）。每个测试用例第一行包含 $n,k$（$1\le n\le2\times10^5$，$0\le k\le6$），第二行包含 $n$ 个整数 $a_i$（$0\le a_i\le63$）。

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

输出格式

对每个测试用例输出一行满足条件的非空子序列数，结果对 $10^9+7$ 取模。

样例输入 1

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

样例输出 1

31
10
10
1
4032
15

数据范围