配点

満点

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

```plain

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

---

Writer: komiya

---

Source Name

Autumn Fest

---