P7717 "EZEC-10" Sequence

> Accurate analytic characterization should be the first breakthrough to try. — command_block, "Pre-exam Tips"

How many different sequences $a$ are there that satisfy: 1. The length of $a$ is $n$. 2. All elements in $a$ are non-negative integers not greater than $k$. 3. There are $m$ constraints of the form $(x_i, y_i, z_i)$ with $x_i < y_i$. Each constraint means $a_{x_i} \oplus a_{y_i} = z_i$ ($\oplus$ denotes the bitwise XOR operation). Two sequences are the same if and only if all their elements are the same. Please output the result modulo $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)))$).

The input has $m+1$ lines: - The first line contains three integers $n, m, k$. - The next $m$ lines each contain three integers $x_i, y_i, z_i$.

Output one line containing the result modulo $10^9+7$.

[Sample $1$ Explanation] There are $6$ sequences: $\{0,1,0\},\{0,1,1\},\{0,1,2\},\{1,0,0\},\{1,0,1\},\{1,0,2\}$. [Data Scale and Conventions] **This problem uses bundled testdata.** - 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): testdata is random. - Subtask 7 (47 points): no special constraints. For $100\%$ of the testdata: $1 \leq n \leq 5 \times 10^5$, $0 \le m \le 5 \times 10^5$, $0 \le z_i