Counting XOR Sequence

Given three integers n, k, and m, you are to count the number of sequences \(a = [a_1, a_2, \dots, a_n]\) such that:

1. The length of \(a\) is \(n\).
2. Each element \(a_i\) satisfies \(0 \le a_i \le k\).
3. There are \(m\) restrictions. The \(i\)th restriction is given as a triple \((x_i, y_i, z_i)\) with \(x_i < y_i\) and it requires that \[ a_{x_i} \oplus a_{y_i} = z_i, \] where \(\oplus\) denotes the bitwise XOR operation.

Two sequences are considered the same if and only if all their elements are equal.

The answer is the total number of such sequences modulo \(1000000007\) (i.e. 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))) = 1000000007. \]).

Note: It is possible that the restrictions are inconsistent; in such a case the answer is 0.

inputFormat

The first line contains three integers \(n\), \(k\), and \(m\).

Then follow \(m\) lines. Each of these \(m\) lines contains three integers \(x_i\), \(y_i\), and \(z_i\) describing a restriction (with \(x_i < y_i\)). Indices are 1-indexed.

outputFormat

Output a single integer: the number of valid sequences modulo \(1000000007\).

sample

3 4 1
1 2 3

20