多边形染色

Flokirie有一个美丽的凸n边形，顶点编号为1~n，每条边长都不相等。 他想把每个顶点都染成1~c中某一颜色，且相邻顶点颜色不能相同。

他想知道所有可行方案共有多少。于是他在纸上算了算，5分钟就解决了这题。 于是他觉得太low了，便定义了以下骚操作。 ① 1 x p：表示第x个顶点必须染颜色p。 ② 2 x p：表示第x个顶点必须不染颜色p。 ③ 3 x y：表示更改第x个顶点与第y个顶点之间边的属性（保证y=x±1，且x,y≠1,n），第x个顶点必须与第y个顶点颜色相同。 现在，他想知道所有可行的方案共有多少种。由于结果可能过大，你只需输出它对987654321取模的结果即可。

第一行，三个正整数n，m，c，表示多边形边数、操作个数、颜色个数。 第2~(m+1)行，每行三个正整数表示一个操作，具体意义见题目描述。

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

3 0 3

6

5 2 5
2 3 4
3 2 3

208

所有测试点满足以下约定：