题目描述

请问有多少个不同的序列 $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$ 取模的结果。

输入格式

输入共 $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$。

【提示】

如果你不知道什么是异或，请点击这里。