1228 : 彩带染色

Description

想象一下你有一条大小为 \(n \times m\) 的大白带，初始第一列上排列着 \(n\) 支不同颜色的刷子，等待着将整条白带染成彩带。

对于每支刷子，你可以将其向右、向上或向下移动多次。被经过的格子会被染上刷子的颜色，但注意每个单元格不能被重复染色，即使是颜色相同的刷子也不行。

你的目标很简单 — 使用一些操作来染色带子上的所有单元格。注意，刷子的初始位置已经染过色。

同时，由于彩带的装饰目的，对染色有一些限制。对于每个限制，其指定同一列中的两个单元格的颜色是否必须相同或不同。

在这些限制下，最终能得到多少种本质不同的彩带？请注意，在这种情况下，我们不考虑翻转或旋转彩带。

Input

第一行包含三个整数：\(n\ (1 \leq n \leq 14)\)，\(m\ (2 \leq m \leq 500)\)，\(r\ (0 \leq r \leq 500)\)，分别表示彩带的宽度、长度和限制数量。

接下来的 \(r\) 行，每行包含四个整数：\(c\ x\ y\ diff\ (1 \leq c \leq m, 1 \leq x < y \leq n, diff \in \{0, 1\})\)。这里，\(diff = 1\) 表示第 \(c\) 列中第 \(x\) 个和第 \(y\) 个单元格的颜色必须不同，否则它们必须相同。

Output

输出本质不同的彩带数量，结果对 \(998244353\) 取模。

Sample

3 5 3
3 2 3 0
4 1 2 0
5 1 3 0
##CASE##
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

19
##CASE##
1514

Hint

Source

Author

SYSU