遗憾的是,问题提出者想不出一个有趣的故事,因此他只是要求你解决以下问题。
给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$,计算子序列中元素的按位 $$$\mathsf{AND}$$$ 在其二进制表示中恰好具有 $$$k$$$ 设置位的非空子序列的数量。答案可能很大,因此输出它对$$$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 \cdot 10^5$$$, $$$0 \le k \le 6$$$) 组成 - 数组的长度和按位 $$$\mathsf{AND}$$$ 计数子序列的设置位数应该有其二进制表示形式。
每个测试用例的第二行由 $$$n$$$ 整数 $$$a_i$$$ ($$$0 \leq a_i \leq 63$$$) 组成 - 数组 $$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 在按位 $$$\mathsf{AND}$$$ 值的二进制表示中恰好具有 $$$k$$$ 设置位的子序列的数量。答案可能很大,因此输出它对$$$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