P4019 Polygon Coloring

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

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 a single integer: the number of feasible colorings modulo $987654321$.

| Test Point ID | $n$ | $m$ | $c$ | |:-:|:-:|:-:|:-:| | $1 \sim 2$ | $3 \le n \le 10$ | $0 \le m \le 10$ | $1 \le c \le 5$ | | $3 \sim 4$ | $3 \le n \le 100$ | $0 \le m \le 30$ | $1 \le c \le 8$ | | $5$ | $3 \le n \le 2 \times 10^3$ | $m = 0$ | $1 \le c \le 10$ | | $6$ | $3 \le n \le 2 \times 10^3$ | $0 \le m \le 100$ | $1 \le c \le 10$ | | $7$ | $3 \le n \le 5 \times 10^4$ | $m = 0$ | $1 \le c \le 10$ | | $8$ | $3 \le n \le 5 \times 10^4$ | $0 \le m \le 500$ | $1 \le c \le 10$ | | $9 \sim 10$ | $3 \le n \le 5 \times 10^4$ | $0 \le m \le 10^3$ | $1 \le c \le 10$ | 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