Problem Background

Flokirie has a beautiful convex polygon with \( n \) vertices, numbered from 1 to \( n \), and each edge has a unique length.

He wants to color each vertex with one of the colors from 1 to \( c \), and adjacent vertices must not have the same color.

Problem Description

He wonders how many feasible coloring schemes there are. After calculating on paper for 5 minutes, he solved the problem.

Feeling it was too simple, he defined the following fancy operations:

1. \( 1 \ x \ p \): The \( x \)-th vertex must be colored \( p \).
2. \( 2 \ x \ p \): The \( x \)-th vertex must not be colored \( p \).
3. \( 3 \ x \ y \): Change the attribute of the edge between the \( x \)-th and \( y \)-th vertices (guaranteed \( y = x \pm 1 \) and \( x, y \neq 1, n \)), the \( x \)-th vertex must have the same color as the \( y \)-th vertex.

Now, he wants to know how many feasible schemes there are. Since the result may be very large, you only need to output the result modulo 987654321.

Input Format

The first line contains three positive integers \( n \), \( m \), and \( c \), representing the number of sides of the polygon, the number of operations, and the number of colors, respectively.

The next \( m \) lines, each containing three positive integers, describe an operation as per the problem description.

Output Format

A single line containing an integer, which is the number of feasible operations modulo 987654321.

Sample Input and Output

Sample Input #1

3 0 3

Sample Output #1

6

Sample Input #2

5 2 5
2 3 4
3 2 3

Sample Output #2

208

Notes

All test cases satisfy the following constraints:

见题面 Input 部分

见题面 Output 部分