Description

最近小小T在学习位运算和快速幂，作为小T的传人，什么简单的与或非还不是简简单单，但是当他学到异或的时候却卡住了，当然并不是因为异或本身定义有什么难的，而是他碰到了一道棘手的难题。这道题是这样的:

现在有$n$个非负整数$a_1, a_2 …… a_n$，他们每个数的数据范围都在$[0, 2^d)$之间，现在你拿这$n$个整数做异或操作既$a_1\ XOR\ a_2\ XOR …… XOR\ a_n$，问你有多少种组合使得整个异或的值为$x$。

当两个组合存在对应的某对整数不同时即被认为是不同的

小小T看到这个题百思不得其解，因为直接枚举所有的组合显然是不切实际的，所以小小T想问问你有没有更好的解法。

$XOR$是指将两个二进制数按位进行异或操作，对应位相同该位为$0$，否则为$1$，如$2\ XOR\ 3 = 1$。

Input Format

题目包含多组样例，在第一行输入一个整数$T$ $(1≤T≤1000)$，代表样例的个数。

对于每组样例，在一行输入三个整数$n ,x , d$ $(1≤n≤10^5)$ $(0≤x<2^{32} )$ $(1≤d≤32)$，$n$表示整数的个数，$x$表示异或后等于的值，$d$表示所有的整数的取值范围只能在$(0 ≤ a_i < 2^d)$。所有样例n的总和不会超过10^6

Output Format

对于每组样例在一行输出一个整数，表示组合的数量。这个值可能会非常大所以需要你对答案和1e9+7取模再输出。

3
1 1 1
2 1 1
100000 123456 24

1
2
391581455