配点

満点

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) % N + 1
b_k = (b_{k-1} * Bmul + Badd) % M + 1
d_k = (d_{k-1} * Dmul + Dadd) % max(N,M) + 1

出力形式

行列をそのまま出力するのは大きくなるので、以下の擬似コードで計算されるハッシュ値を一行に出力せよ。

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

入力例 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