P17788 樽见不是罪过

『如果我不做些什么的话，一定在那个瞬间，这份缘分就断掉了吧。』 『尽可能地思考，像处理易碎品那样细致地……那是很容易就损坏的东西。』

给定 $n,k$ 和一个长度为 $k$ 的序列 $x_{0\sim k-1}$。定义一个正整数序列 $A_{0\sim |A|-1}$ 是好的，当且仅当满足以下条件： 1. $\sum\limits_{i=0}^{|A|-1}A_i = n$。 2. 对 $i\in [0,|A|-1]$，有 $A_i \text{ AND } x_{i\bmod k}= A_i$。其中 $\text{AND}$ 为二进制与。 对于一个好的序列 $A$，定义其价值 $f(A) = \prod\limits_{i=0}^{|A|-1}(A_i+A_{(i+1)\bmod |A|})$。 求所有好的序列价值和，即 $\sum\limits_{\text{A is good}}^{}f(A)$。 结果对 $10^9+7$ 取模。

第一行一个整数 $T$，表示测试点组数。 接下来 $T$ 组数据： 每组第一行两个整数 $n,k$。 每组第二行 $k$ 个整数 $x_{0\sim k-1}$。

共 $T$ 行，每行一个整数表示每一组测试数据的答案。

我们再当一次朋友吧，小岛。 保证 $1\le T\le 10,1 \le n \le 5\times 10^4,1 \le k \le 10,0 \le x_i < 2^{30},1\le \sum n \le 10^5$。