配点

満点

120

部分点

40

---

问题文

存在一个 $N \times M$ 的矩阵 $\\{X_{i,j}\\}_{1 ≤ i ≤ N, 1 ≤ j ≤ M}$，初始状态下所有元素均为0。

给定长度为 $Q$ 的整数序列 $\\{a_i\\}, \\{b_i\\}, \\{d_i\\}$。求在对每个$k, i, j (1≤ k ≤ Q, 1 ≤ i ≤ N, 1 ≤ j ≤ M )$，将 $X_{i,j}$ 加上 $max(\\ 0,\\ d_k - (|a_k - i| + |b_k - j|)\\ )$ 的操作后得到的矩阵的每个元素。

---

输入格式

因为 $Q$ 很大，所以给出输入的种子。输入的格式如下。

$N\\ M\\ Q\\ a_1\\ Amul\\ Aadd\\\\ b_1\\ Bmul\\ Badd\\\\ d_1\\ Dmul\\ Dadd$

对于 $1<k ≤ Q$，$a_k,\\ b_k,\\ d_k$ 分别由以下公式生成。

$a_k = (a_{k-1} \* Amul + Aadd)$ $b_k = (b_{k-1} \* Bmul + Badd)$ $d_k = (d_{k-1} \* Dmul + Dadd)$

---

输出格式

直接输出矩阵会很大，所以输出使用下面的伪代码计算得到的哈希值。

P := $10^9 + 7$ mod := $10^9 + 9$ hash := $0$ for i in $1..N$ for j in $1..M$ hash := (hash * P + $X_{i,j}$) % mod

---

制约条件

• $1 ≤ N ≤ 1000$
• $1 ≤ M ≤ 1000$
• $1 ≤ Q ≤ 10^6$
• $1 ≤ a_1 ≤ N$
• $1 ≤ b_1 ≤ M$
• $1 ≤ d_1 ≤ max(N,M)$
• $0 ≤ Amul,\\ Bmul,\\ Dmul,\\ Aadd,\\ Badd,\\ Dadd ≤ 10^4$
• 输入值均为整数。

此问题的判定有一个40分的测试用例组。该组中的测试用例除了满足上述约束条件外，还满足以下约束条件。

• $N = 1$

---

输入例子1

3 4 2
3 2 1
1 2 0
4 0 2

输出例子1

999996819

在这个例子中$\\{a_i\\}=\\{3,2\\},\\ \\{b_i\\}=\\{1,3\\},\\ \\{d_i\\}=\\{4,3\\}$。

当$k=1$时，对矩阵的每个元素分别加上以下值。

2 1 0 0
3 2 1 0
4 3 2 1

当$k=2$时，对矩阵的每个元素分别加上以下值。

0 1 2 1
1 2 3 2
0 1 2 1

经过上述操作后，最终矩阵$X$变为以下形式。

2 2 2 1
4 4 4 2
4 4 4 2

对该矩阵使用上述方法计算哈希值得到999996819。

---

输入例子2

1000 999 1000000
123 4567 8910
314 1592 6535
47 4747 4747

输出例子2

394300610

---

输入例子3

1 111 222
1 11 1111
33 44 55
66 77 88

输出例子3

79966854

---

出题人：komiya

---

出处

秋季节日