Counting Valid Colorings on a Path with Constraints

You are given a path graph with n vertices numbered from 1 to n and k available colors. Each vertex is to be colored with one of the k colors. In addition, there are q operations imposing extra constraints on the colorings. The operations are described as follows:

• 1 x p: Vertex x must be colored with color p.
• 2 x p: Vertex x must not be colored with color p.
• 3 x y: Modify the edge between vertices x and y (it is guaranteed that y=x±1 and x,y≠1,n) so that x and y are forced to have the same color.

Your task is to count the number of valid colorings that satisfy all the given constraints. Since the answer can be large, output it modulo \(987654321\).

The key idea is to process the constraints in two parts:

1. For each vertex, update its set of allowed colors based on operations of type 1 and 2.
2. For operations of type 3, which force two adjacent (interior) vertices to have the same color, merge the vertices into connected components and take the intersection of their allowed colors.

If any vertex (or merged component) has no allowed colors, the answer is 0. Otherwise, for each component (or singleton vertex not merged with any other), if \(S\) is the intersection of allowed colors then the number of ways to color that component is \(|S|\). The final answer is the product of these possibilities modulo \(987654321\).

inputFormat

The first line contains three integers n, k, and q — the number of vertices, the number of available colors, and the number of operations, respectively.

Each of the following q lines describes an operation in one of the three forms:

• 1 x p
• 2 x p
• 3 x y

It is guaranteed that for operations of type 3, y = x ± 1 and x, y ≠ 1, n.

outputFormat

Output a single integer — the number of valid colorings modulo \(987654321\).

sample

5 3 3
1 2 1
2 4 2
3 3 4

18