The annual robot race will take place in Berland today. Ivan is one of its participants. Before the start, he decided to find out what the field where the robots will compete looks like. The race course is a rectangle n * m divided into nm unit cells. The rows of the rectangle are numbered from 1 to n, and the columns are numbered from 1 to m. We will denote the cell located at the intersection of the i-th row and the j-th column as (i, j). There can be a barrier between each pair of adjacent cells on the field.

n robots take part in the race. Initially, they are located in the cells of the first column: (1, 1), (2, 1), ..., (n, 1). The finish is the cell (n, m). When the race starts, each robot starts moving towards the finish line. From the cell (i, j) the robot can move either to the cell (i + 1, j), or to the cell (i , j + 1). If there is no barrier between the cell in which the robot is located and the cell in which it is moving, the robot moves to the adjacent cell instantly. If there is a barrier between the cells, the robot spends one second moving between them.

Ivan managed to look around the competition field and remembered some information about it. Namely, about some pairs of neighbouring cells, he knows for sure whether there is a barrier between them. He is also confident that the competition field is fair. Ivan wondered how many fields exist that satisfy these conditions. Since the answer can be very large, Ivan is only interested in the remainder of the division by 998244353.

Input

The first line contains two integers n and m - the size of the field for the match (1 ≤ n ≤ 5, 1 ≤ m ≤ 15). The second line contains a single number k - the number of pairs of cells about which Ivan knows whether there is a barrier between them (0 ≤ k ≤ 2nm - n - m).

Each of the following k lines contains five integers r1, c1, r2, c2 and w (1 ≤ r1 ≤ r2 ≤ n, 1 ≤ c1 ≤ c2 ≤ m, 0 ≤ w ≤ 1). If w = 0, then there is no barrier between cells (r1, c1) and (r2, c2). If w = 1, then there is a barrier between the cells. It is guaranteed that cells (r1, c1) and (r2, c2) are adjacent. It is guaranteed that no pair of neighbouring cells will be mentioned twice in the input.

Output

Print a single number - the remainder of the division by 998244353 of the number of fair fields that satisfy all Ivan's conditions.

Example

Test from the example, solid lines indicate a barrier, and dashed lines indicate its absence.