U187400 胜利的方程式

2021.10.31模拟赛T2 https://www.luogu.com.cn/problem/CF1557C

决斗者Vis现在写下了胜利的方程式。 现在场上有 $n$ 个要素 $a_1-a_n$ ，每个要素可能取 $[0,2^k-1]$ 内的整数。Vis的得分是 $a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}...\operatorname{xor}a_n$，而对手的得分只有$a_1 \& a_2 \& a_3 \& ... \& a_n$，虽然Vis觉得他赢面很大，但是鉴于他之前翻车的经历，他还是想知道，有多少种情况，他无法战胜对手（即，分数不严格大于对手）。 即，不定方程 $a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}...\operatorname{xor}a_n \le a_1 \& a_2 \& a_3 \& ... \& a_n (a_i \in [0,2^k-1])$ 有多少组解。 答案可能很大，请输出答案 $\operatorname{mod}10^9+7 $的值。

第一行一个数 $t$ 表示数据组数。 接下来 $t$ 行每行两个数 $n$ 与 $k$。

$t$ 行，每行一个数，表答案。

对于 $20\%$ 的数据 $n*k\le20$。 对于 $50\%$ 的数据 $n,k\le500$。 对于另外 $20%$ 的数据 $k\le10$。 对于另外 $20%$ 的数据 $n\le4$ 。 对于 $100%$ 的数据 $n,k\le200000，t\le5$。