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

n \leq 50000 ,m \leq 1000 , c\leq 10

Flokirie