题目描述

33DAI 拿到了一个 $n$ 行 $m$ 列的二维数组。第 $i$ 行第 $j$ 列的元素用 $(i,j)$ 表示。

他需要进行 $Q$ 次激发操作。每次激发操作都会给你三个参数 $x,y,k$，表示需要把与 $(x,y)$ 的曼哈顿距离不超过 $k$ 的点都增加 $1$。

简单来说，如果 $(a,b)$ 满足 $|a-x|+|b-y|\le k$，那么就把 $(a,b)$ 位置上的数增加 $1$。

请你看看最终矩阵会变成什么样。

矩阵太大了，你只需要输出 $(\sum_{i=1}^n\sum_{j=1}^m (a_{i,j}+i+j)^2)\bmod (10^9+7)$，即所有位置的“数和他们坐标之和的平方”之和模 $(10^9+7)$ 之后的结果。

输入格式

第一行三个数，$n,m,Q$。

接下来 $Q$ 行，第 $i$ 行为空格隔开的三个整数 $x,y,k$，表示一次操作。

输出格式

一个数，即题目要求的答案。

8 8 3
3 3 3
7 8 2
8 1 2

6515

下面是修改之后的二维数组，为了让大家看得更清楚，下面用 # 表示 $1$，. 表示 $0$。

.###....
#####...
######..
#####...
.###...#
#.#...##
##...###
###...##

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m,Q,k \le 5000$，$1\le x\le n$，$1\le y \le m$。

• 子任务 1（30 分）：$1\le n,m,Q,k\le 10$。
• 子任务 2（30 分）：$Q=1$。
• 子任务 3（40 分）：没有特殊限制。