Background

Accurate analytic characterization should be the first breakthrough to try.

— command_block, "Pre-exam Tips"

Problem Description

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$ .

Input Format

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 Format

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

3 1 2
1 2 1

6

5 1 12
1 2 3

26364

Hint

[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<2^{30}$, $1 \leq k< 2^{30}$, $1\le x_i,y_i\le n$.

[Hint]

If you do not know what XOR is, please click here。

Translated by ChatGPT 5