Coloring Tape
Description
Imagine you have a large tape of size $n \times m$, with $n$ brushes dipped in different colors arranged in the first column, waiting to color the entire tape.
This image shows an example, where the lines represent the movement path of the brushes. For each brush, you can move it to the right, up or down for several times. Each cell cannot be colored twice, even if the colors are the same. Your goal is simple - to color all cells of the tape using some operations. Note that the initial positions of the brushes are already colored.
Meanwhile, due to the decorative purpose of the tape, there are some restrictions on coloring. For each restriction, we will provide two cells in the same column and indicate whether the colors of these two cells must be the same or different.
Under these restrictions, how many different color arrangements can the final tape have? Note that in this case, we do not consider flipping or rotating the tape.
The first line contains three integers: $n\ (1 \leq n \leq 14)$, $m\ (2 \leq m \leq 500)$, and $r\ (0 \leq r \leq 500)$, representing the width, length, and number of restrictions of the tape, respectively.
Next, there are $r$ lines, each containing four integers: $c\ x\ y\ diff\ (1 \leq c \leq m, 1 \leq x < y \leq n, diff \in \{0, 1\})$. Here, $diff = 1$ means that the colors of the $x$-th and $y$-th cells in column $c$ must be different, otherwise they must be the same.
Output the result modulo $998244353$.
Input
The first line contains three integers: $n\ (1 \leq n \leq 14)$, $m\ (2 \leq m \leq 500)$, and $r\ (0 \leq r \leq 500)$, representing the width, length, and number of restrictions of the tape, respectively.
Next, there are $r$ lines, each containing four integers: $c\ x\ y\ diff\ (1 \leq c \leq m, 1 \leq x < y \leq n, diff \in \{0, 1\})$. Here, $diff = 1$ means that the colors of the $x$-th and $y$-th cells in column $c$ must be different, otherwise they must be the same.
Output
Output the result modulo $998244353$.
3 5 3
3 2 3 0
4 1 2 0
5 1 3 0
5 10 10
9 3 4 1
2 4 5 0
7 2 3 0
9 2 3 0
6 3 5 0
6 2 4 1
2 4 5 0
1 1 3 1
7 2 4 0
10 2 3 0
4 2 0
19
1514
17