「EZEC-10」序列

> 精准的解析刻画，是应该首先尝试的突破口。 ——command_block 《考前小贴士》

请问有多少个不同的序列 $a$，满足： 1. $a$ 的长度为 $n$。 2. $a$ 中的元素均为不大于 $k$ 的非负整数。 3. 满足 $m$ 组形如 $(x_i,y_i,z_i)$ 且 $x_i<y_i$ 的限制，每组限制的意义为 $a_{x_i} \oplus a_{y_i} = z_i$ （$\oplus$ 表示按位异或运算）。 两个序列相同，当且仅当它们所有元素均相同。 请输出答案对 $10^9+7$ []($114514\times(114\times5\times14+((1+145)\times(1+4)+(1\times14+5-1+4)))+(114\times514+(11\times(451+4)+(-1+145+14)))$)取模的结果。

输入共 $m+1$ 行： - 第一行三个数，$n,m,k$。 - 接下来 $m$ 行，每行 $3$ 个数，$x_i,y_i,z_i$。

输出仅一行，表示答案对 $10^9+7$ 取模的结果。

3 1 2
1 2 1

6

5 1 12
1 2 3

26364

【样例 $1$ 说明】 共有 $6$ 种序列：$\{0,1,0\},\{0,1,1\},\{0,1,2\},\{1,0,0\},\{1,0,1\},\{1,0,2\}$。 【数据规模与约定】 **本题采用捆绑测试。** - Subtask 1（1 point）：$n=1$。 - Subtask 2（5 points）：$m=0$。 - Subtask 3（15 points）：$n,m,k\le 5$。 - Subtask 4（10 points）：$z_i=0$。 - Subtask 5（20 points）：$k\le 16$。 - Subtask 6（2 points）：数据随机。 - Subtask 7（47 points）：无特殊限制。 对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$0 \le m \le 5 \times 10^5$，$0 \le z_i<2^{30}$，$1 \leq k< 2^{30}$，$1\le x_i,y_i\le n$。 【提示】 如果你不知道什么是异或，请点击[这里](https://baike.baidu.com/item/%E5%BC%82%E6%88%96#:~:text=%E5%BC%82%E6%88%96%E4%B9%9F%E5%8F%AB%E5%8D%8A,%E8%AE%A4%E4%BD%9C%E4%B8%8D%E8%BF%9B%E4%BD%8D%E5%8A%A0%E6%B3%95%E3%80%82&text=%E7%A8%8B%E5%BA%8F%E4%B8%AD%E6%9C%89%E4%B8%89%E7%A7%8D%E6%BC%94%E7%AE%97%E5%AD%90%EF%BC%9AXOR%E3%80%81eor%E3%80%81%E2%8A%95%E3%80%82)。