Race of robots

The annual race of robots takes place today in Berland. Ivan is one of its participants. Before the race starts, he wants to find out what the racing field looks like.

The racing field is a rectangle of size $n \times m$ divided into $nm$ unit cells. Rows are numbered from $1$ to $n$, and columns are numbered from $1$ to $m$. We denote by $(i, j)$ the cell in row $i$ and column $j$. There can be a barrier between each pair of adjacent cells.

There are $n$ robots. Before the race, they are located in the cells of the first column: $(1, 1), (2, 1), \ldots, (n, 1)$. The finish is the cell $(n, m)$. When the race begins, each robot moves toward the finish. From cell $(i, j)$, a robot can move either to $(i + 1, j)$ or to $(i, j + 1)$. If there is no barrier between the two cells, the robot moves between them immediately. Otherwise, the move takes one second.

Each robot knows the locations of all barriers in advance and takes a path that needs the minimum time to reach the finish. Robots are very small, so any number of them may stay in the same cell. The field is called fair if all robots need the same time to reach the finish.

Ivan has seen the field and remembers some information about it. For some pairs of adjacent cells, he knows for certain whether there is a barrier between them. He is also sure that the field is fair. Ivan wants to know how many fields satisfy all of these conditions. Since the answer may be very large, output it modulo 998244353.

The first line contains two integers $n$ and $m$, the size of the field ($1 \le n \le 5$, $1 \le m \le 15$).

The second line contains a single integer $k$, the number of pairs of cells for which Ivan knows the barrier status ($0 \le k \le 2nm - n - m$).

Each of the next $k$ lines contains five integers $r_1$, $c_1$, $r_2$, $c_2$ and $w$ ($1 \le r_1 \le r_2 \le n$, $1 \le c_1 \le c_2 \le m$, $0 \le w \le 1$). If $w = 0$, there is no barrier between cells $(r_1, c_1)$ and $(r_2, c_2)$. If $w = 1$, there is a barrier between them. The two cells are always adjacent, and no pair of cells is listed more than once.

Output one integer, the number of fair fields that satisfy all of Ivan's conditions, modulo 998244353.

Illustration for the sample test. Solid lines denote a barrier, dashed lines denote its absence.