题目描述

$Sunny\ bunny$ 决定手动对图片加密。

他手头上有一张长 $n$ 个像素点，宽 $m$ 个像素点的图片，并且。图片的行按照 $1,2,3,\dots,n$ 编号，列按照 $1,2,3,\dots,m$ 编号。我们将初始的图片编号为第 $0$ 张图片，并用矩阵 $(A_0)_{n\times m}$ 来表示这张图片， $(A_0)_{ij}$ 表示原图第 $i$ 行、第 $j$ 列交叉处的像素的颜色。对于之后会遇到的更多图片，我们也以这种矩阵的方式来表示。

然而，由于 $Sunny\ bunny$ 在现实中并没能和伙伴们玩耍，因此最开始的图片是几乎空白的：

$$(A_0)_{ij}= \begin{cases} 1&i=j\newline 0&i\neq j \end{cases}$$

接下来， $Sunny\ bunny$ 将要进行 $q$ 次加密操作。第 $k$ 次操作会在第 $k-1$ 张图片的基础上进行，产生的新的图片被编号为第 $k$ 张。相应地，我们也可以通过第 $k-1$ 张图片的矩阵 $(A_{k-1})_{n\times m}$ ，生成第 $k$ 张图片的矩阵 $(A_k)_{n\times m}$ 。

具体地，进行第 $k$ 次操作时， $Sunny\ bunny$ 会给出 $l_k,r_k,c_k,d_k$ ，并在矩阵 $(A_{k-1})_{n\times m}$ 的基础上生成一个新的矩阵 $(A_k)_{n\times m}$ ：

$j\not\in [l_k,r_k]$ ，则 $(A_k)_{ij}=d_k (A_{k-1})_{ij}$ ； $j\in [l_k,r_k]$ ，则 $(A_k)_{ij}=d_k \sum_{t=l_k}^j(c_k)^{j-t}(A_{k-1})_{it}$ 。

但是，为了避免加密过后整张图片变得过于难以分辨， $Sunny\ bunny$ 需要对加密操作进行限制：每个格子被修改的次数不会太多。

形式化地，他保证，对于所有 $1\le i\le m$ ，都有：$$\sum_{k=1}^q[i\in [l_k,r_k]]\le s$$

其中 $s$ 是一个较小的常数。此处，我们用 $[P]$ 量化命题 $P$ 的真假：$$[P]=\begin{cases} 1&P\newline 0&\neg P \end{cases}$$

容易发现，只要知道了 $Sunny\ bunny$ 的 $q$ 次操作的所有参数， $I.W.\ bunny$ 就可以反过来从加密后的图片解密得到最初的图片。因此，这种加密方式可以说是"无损"的。

然而，由于图片实在是太大了，文件传输速度限制了 $I.W. bunny$ 一时半会儿还收不到这张图片。为了保证最终 $I.W. bunny$ 收到的图片不被篡改， $Sunny\ bunny$ 决定先给她发一段校验码。

对于一张 $n\times m$ 的，且满足 $n\le m$ 的图片，假如我们用矩阵 $B_{n\times m}$ 来表示它， $B_{ij}$ 表示第 $i$ 行与第 $j$ 列交叉处的像素的颜色，我们可以定义它的校验码 $f(B)$ 为：$$f(B)=\left(\sum_{S\subseteq{1,2,3,\dots,m},|S|=n}\det B_S\right)\bmod (10^9+7)$$

此处，我们定义 $B_S$ 为 $B$ 的所有行与 $S$ 中元素作为标号对应的列的交叉处生成的一个 $n\times |S$ | $的矩阵。形式化地，我们令$ | $S|=k$ ，而令 $S$ 中元素从小到大为 $s_1,s_2,\dots,s_k$ ，则有：$$(B_S){ij}=B{i,s_j}$$

不过， $Sunny\ bunny$ 这才意识到，他做的加密操作次数实在是太多了！现在，他只好向你求助：你能够帮他算出校验码 $f(A_k)$ 吗？之后对于图片的加密操作，他会一个人承担的。

【提示】

$Binet-Cauchy$ 定理：对于一个 $n\times m$ 且 的矩阵 $A$ 和 $m\times n$ 的矩阵 $B$ ，该定理指出：$$\det AB=\sum_{S\subseteq {1,2,3,\dots,m},|S|=n} \det A_S\det B^S$$

此处，我们定义 $A_S$ 为 $A$ 的所有行与 $S$ 中元素作为标号对应的所有列的交叉处生成的 $n\times |S|$ 的矩阵， $B^S$ 为 $B$ 中所有列与 $S$ 中元素作为标号对应的所有行的交叉处生成的 $|S|\times n$ 的矩阵。

形式化地，令 $|S|=k$ ，令 $S$ 中元素从小到大为 $s_1,s_2,s_3,\dots,s_k$ ，则：$$(A_S){ij}=A{i,s_j},(B^S){ij}=B{s_i,j}$$

输入格式

第一行三个正整数 $n,m,q$ ，分别表示图片的长度、宽度和 $Sunny\ bunny$ 将要进行的加密操作次数。

接下来 $q$ 行，每行四个正整数 $l_k,r_k,c_k,d_k$ ，表示 $Sunny\ bunny$ 第 $k$ 次加密操作时使用的参数。

输出格式

输出仅一行一个非负整数，表示最终图片的校验码 $f(A_k)$ 的值。

数据范围

对于所有测试点： $2\le n\le m\le 2\times 10^5,1\le s\le 8,1\le q\le sm$ ，且对于所有的 $1\le k\le q,1\le l_k < r_k\le m,1\le c_k,d_k < 10^9+7$ 。

每个测试点的具体限制见下表：

测试点编号	$m \le$	$s \le$	$c_k,d_k$	特殊限制
$1\sim 2$	$10$	$8$	$< 10^9+7$	$m-n\le 1$
$3$	$100$		$=1$
$4$			$< 10^9+7$
$5\sim 7$	$2\times 10^5$	$1$	$=1$	无
$8\sim 10$		$3$
$11\sim 13$		$5$
$14\sim 15$			$< 10^9+7$
$16\sim 20$		$8$	$=1$
$21\sim 25$			$< 10^9+7$

输入样例 1

2 3 3
1 3 1 1
2 3 1 1
1 2 1 1

输出样例 1

5

输入样例 2

3 5 3
1 4 2 1
3 5 3 1
1 4 1 1

输出样例 2

57

样例解释

对于样例 $1$ ：

初始时，矩阵 $A_0$ 为：

$$\begin{bmatrix} 1&0&0\newline 0&1&0 \end{bmatrix}$$

进行加密操作 $1$ 之后，矩阵 $A_1$ 为：$$\begin{bmatrix} 1&1&1\newline 0&1&1 \end{bmatrix}$$

进行加密操作 $2$ 之后，矩阵 $A_2$ 为：$$\begin{bmatrix} 1&1&2\newline 0&1&2 \end{bmatrix}$$

进行加密操作 $3$ 之后，矩阵 $A_3$ 为：$$\begin{bmatrix} 1&2&2\newline 0&1&2 \end{bmatrix}$$

最终，我们要求 $f(A_3)=\det A_3(\\{1,2\\})+\det A_3(\\{1,3\\})+\det A_3(\\{2,3\\})$ 。举一个例子：$$A_3({2,3})=\begin{bmatrix} 2&2\newline 1&2 \end{bmatrix}$$

它的行列式为 $2$ 。

$A_3(\\{1,2\\})$ 和 $A_3(\\{1,3\\})$ 类似。最终我们得到 $f(A_3)=1+2+2=5$ 。