#P18433. Coloring Tape

Coloring Tape

Coloring Tape

有一条大小为 n×mn\times m 的纸带。第一列的每一行各有一把刷子,共 nn 把;每把刷子蘸着一种颜色,且这些颜色两两不同。它们初始所在的格子已经被染上各自的颜色。

你可以让每把刷子向右、向上或向下移动若干次。每移动一步,刷子将到达的格子染成自己的颜色。每个格子都不能被重复染色,即使两次使用的颜色相同也不允许。目标是将纸带的所有格子染色。

下图是一个例子,其中的线段表示各把刷子的移动路径。

原题纸带染色与刷子移动路径

出于装饰需要,还给出了若干限制。每条限制指定同一列中的两个格子,并要求它们的颜色必须相同或必须不同。

满足这些限制的最终染色方案共有多少种?按最终各格子的颜色区分方案;翻转或旋转后的纸带不作等同处理。请输出方案数对 998244353998244353 取模的结果。

输入格式

第一行包含三个整数 n,m,rn,m,r(1≤n≤141\le n\le14,2≤m≤5002\le m\le500,0≤r≤5000\le r\le500),依次表示纸带的行数、列数以及限制数。

接下来 rr 行,每行包含四个整数 c,x,y,diffc,x,y,\mathrm{diff}(1≤c≤m1\le c\le m,1≤x<y≤n1\le x<y\le n,diff∈{0,1}\mathrm{diff}\in\{0,1\})。

  • 若 diff=1\mathrm{diff}=1,则第 cc 列第 xx 行和第 yy 行格子的颜色必须不同。
  • 若 diff=0\mathrm{diff}=0,则这两个格子的颜色必须相同。

输出格式

输出一个整数,表示满足条件的最终染色方案数对 998244353998244353 取模的结果。

原样例

样例 1:

3 5 3
3 2 3 0
4 1 2 0
5 1 3 0
19

样例 2:

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
1514

样例 3:

4 2 0
17