暂无测试数据。

小 A 从梦中醒了过来。

小 A 依稀记得他的 npy 送给他的礼物——一个 $n \times n$ 的数字矩阵。小 A 还惊奇地发现，这个矩阵中每个数字都满足 $0 \le x < 2^q$。小 A 还能记起当时他的激动与喜悦，可是他怎么也回忆不起那个矩阵了。

然而小 A 还记得其他的一些事情——比如这个矩阵的每一行的异或和，还有矩阵第一列的异或和。小 A 希望知道，在这种情况下，满足条件的矩阵一共有多少种。

输入格式

输入第一行三个整数 $n, k, q$，分别表示矩阵的大小，第一列数字的异或和和数字规模。

第二行 $n$ 个数字 $a_i$，表示第一行至最后一行的异或和。

输出格式

输出一个数字表示答案，答案对 $10^9+7$ 取模。

数据范围

对于 $30\%$ 的 数据 $n = 2$, $a_i,k \le 3$, $q \le 2$；

对于 $50\%$ 的数据 $n \le 4$, $a_i,k \le 10^6$, $q \le 20$；

对于 $70\%$ 的数据 $n \le 2000$, $a_i,k \le 10^9$, $q \le 30$；

对于 $100\%$ 的数据 $2 \le n \le 500000$, $0 \le a_i,k \le 10^9$, $q \le 30$, $0 \le a_i,k < 2^q$。

2 1 2
1 2

4