题目描述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

出题Author

SYSU

来源Source