题目描述

给定一个 $h$ 行 $w$ 列的网格，每个单元格需填入 $[1, m]$ 范围内的整数。存在 $n$ 条约束，每条约束指定一个子矩阵（左上角 $(x_1,y_1)$，右下角 $(x_2,y_2)$），要求该子矩阵内所有单元格的最大值恰好等于 $v$。形式化地，设网格矩阵为 $A$，$A_{i,j}$ 表示第 $i$ 行第 $j$ 列的值，每条约束要求：

$$\max\{A_{i,j} \mid x_1 \leq i \leq x_2,\ y_1 \leq j \leq y_2\} = v$$

计算满足所有约束的网格填数方案数量，结果对 $10^9 + 7$ 取模。

输入格式

第一行输入四个整数 $h, w, m, n$ ($1\leq h,w,m \leq 10000$, $0 \leq n \leq 10$)，分别表示网格行数、列数、数值上限、约束数。

接下来 $n$ 行，每行五个整数 $x_1, y_1, x_2, y_2, v$ ($1\leq x_1,x_2 \leq h$, $1\leq y_1,y_2 \leq w$, $1\leq v \leq m$)，描述一条约束。

输出格式

一行一个整数，表示方案数模 $10^9 + 7$ 的结果。

样例输入

2 3 2 1
1 2 2 3 2

样例输出

60

数据范围

对于 $20\%$ 的数据，$h,w,n,m \leq 3$；

另有 $10\%$ 的数据满足 $n = 0$；

另有 $20\%$ 的数据满足 $n = 1$；

对于 $100\%$ 的数据，$h,w,n,m \leq 10000, 1\leq v \leq m, 0\leq n\leq 10$。