题目描述

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$ 的结果。

3 0 3

6

5 2 5
2 3 4
3 2 3

208

提示

保证对于 $100\%$ 的数据，$3\le n\le 5\times 10^4,0\le m\le10^3, 1\le c\le10$。