Description

Flokirie has a beautiful convex $n$-gon with vertices numbered from $1$ to $n$. Each edge connects vertex $i$ and $i+1$, and in particular, vertex $n$ is connected to vertex $1$.

He wants to color each vertex with some color $k$ ($k \le c$), i.e., each vertex is assigned a color from $1$ to $c$, and adjacent vertices must not have the same color.

He wants to know how many feasible colorings there are. He calculated it on paper and solved it in $5$ minutes.

He thought that was too trivial, so he defined the following “fancy” operations:

1. 1 x p: vertex $x$ must be colored with color $p$.
2. 2 x p: vertex $x$ must not be colored with color $p$.
3. 3 x y: change the attribute of the edge between vertex $x$ and vertex $y$ (guaranteed that $y = x \pm 1$ and $x, y \ne 1, n$), i.e., vertex $x$ must have the same color as vertex $y$.

Now, he wants to know the total number of feasible colorings after applying all operations. Since the result may be large, output it modulo $987654321$.

Input Format

The first line contains three positive integers $n$, $m$, $c$, representing the number of sides of the polygon, the number of operations, and the number of colors.

Each of the following $m$ lines contains three positive integers describing one operation, as defined above.

Output Format

Output a single integer: the number of feasible colorings modulo $987654321$.

3 0 3

6

5 2 5
2 3 4
3 2 3

208

Hint

It is guaranteed that for $100\%$ of the testdata, $3 \le n \le 5 \times 10^4$, $0 \le m \le 10^3$, $1 \le c \le 10$.

Translated by ChatGPT 5