P4019 多边形染色

Flokirie 有一个美丽的凸 $n$ 边形，顶点编号为 $1$ 到 $n$，每条边连接顶点 $i$ 和 $i+1$。特别的，顶点 $n$ 与顶点 $1$ 相连 他想把每个顶点都染成某一种颜色 $k(k \le c)$，且相邻顶点颜色不能相同。 他想知道所有可行方案共有多少。于是他在纸上算了算，$5$ 分钟就解决了这题。 于是他觉得太 low 了，便定义了以下骚操作。 1. `1 x p`：表示第 $x$ 个顶点必须染颜色 $p$。 2. `2 x p`：表示第 $x$ 个顶点必须不染颜色 $p$。 3. `3 x y`：表示更改第 $x$ 个顶点与第 $y$ 个顶点之间边的属性（保证 $y=x±1$，且 $x,y≠1,n$），即第 $x$ 个顶点必须与第 $y$ 个顶点颜色相同。 现在，他想知道所有可行的方案共有多少种。由于结果可能过大，你只需输出它对 $987654321$ 取模的结果即可。

第一行，三个正整数 $n$，$m$，$c$，表示多边形边数、操作个数、颜色个数。 之后 $m$ 行，每行三个正整数表示一个操作，具体意义见题目描述。

一行一个整数，为所有可行操作和模上 $987654321$ 的结果。

| 测试点编号 | $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\le500$ | $1\le c\le 10$ | | $9\sim 10$ | $3\le n\le 5\times 10^4$ | $0\le m\le10^3$ | $1\le c\le 10$ | 保证对于 $100\%$ 的数据，$3\le n\le 5\times 10^4,0\le m\le10^3, 1\le c\le10$。