#P18433. Coloring Tape
Coloring Tape
Coloring Tape
有一条大小为 的纸带。第一列的每一行各有一把刷子,共 把;每把刷子蘸着一种颜色,且这些颜色两两不同。它们初始所在的格子已经被染上各自的颜色。
你可以让每把刷子向右、向上或向下移动若干次。每移动一步,刷子将到达的格子染成自己的颜色。每个格子都不能被重复染色,即使两次使用的颜色相同也不允许。目标是将纸带的所有格子染色。
下图是一个例子,其中的线段表示各把刷子的移动路径。

出于装饰需要,还给出了若干限制。每条限制指定同一列中的两个格子,并要求它们的颜色必须相同或必须不同。
满足这些限制的最终染色方案共有多少种?按最终各格子的颜色区分方案;翻转或旋转后的纸带不作等同处理。请输出方案数对 取模的结果。
输入格式
第一行包含三个整数 (,,),依次表示纸带的行数、列数以及限制数。
接下来 行,每行包含四个整数 (,,)。
- 若 ,则第 列第 行和第 行格子的颜色必须不同。
- 若 ,则这两个格子的颜色必须相同。
输出格式
输出一个整数,表示满足条件的最终染色方案数对 取模的结果。
原样例
样例 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