P4521 [COCI 2017/2018 #4] Automobil

米尔科在他的车后座上发现了一个有 $N$ 行 $M$ 列的矩阵。矩阵的第一行由数字 $1, 2, \cdots, M$ 组成，第二行由数字 $M+1, M+2, \cdots, 2M$ 组成，依此类推，直到第 $N$ 行，其由数字 $(N-1)M + 1, (N-1)M + 2, \cdots, NM$ 组成。 例如，对于 $N = 3$ 和 $M = 4$： | - | - | - | - | | :----------: | :----------: | :----------: | :----------: | | **1** | **2** | **3** | **4** | | **5** | **6** | **7** | **8** | | **9** | **10** | **11** | **12** | 这样的矩阵对他来说不够有趣，所以他选择了一行或一列 $K$ 次，并将其值乘以一个非负整数。 自然地，现在他想知道矩阵中所有值的和。由于这个和可能非常大，米尔科将对其取模 $10^9 + 7$。帮助米尔科回答这个问题。

输入的第一行包含任务中的数字 $N$（$1 \le N \le 10^6$）, $M$（$1\le M\le 10^6$）和 $K$（$1\le K\le 10^3$）。 - 或者是将第 $X$ 行乘以 $Y$，形式为 `R X Y`，其中 `R` 表示行乘法，$X$ 是一个正整数（$1\le X\le N$），$Y$ 是一个非负整数（$0 \le Y \le 10^9$）。 - 或者是将第 $X$ 列乘以 $Y$，形式为 `S X Y`，其中 `S` 表示列乘法，$X$ 是一个正整数（$1\le X\le M$），$Y$ 是一个非负整数（$0 \le Y \le 10^9$）。

你必须输出矩阵最终值的和对 $10^9 + 7$ 取模的结果。

在总共价值 $50$ 分的测试用例中，将满足 $1 \le N, M \le 10^3$。 **第一个测试用例的说明**：在将第二行乘以 $4$，第四列乘以 $1$，第三行乘以 $2$，再次将第二行乘以 $0$ 之后，最终矩阵如下所示： | - | - | - | - | | :----------: | :----------: | :----------: | :----------: | | **1** | **2** | **3** | **4** | | **0** | **0** | **0** | **0** | | **18** | **20** | **22** | **24** | 最终矩阵中元素的和为 $1 + 2 + 3 + 4 + 0 + 0 + 0 + 0 + 18 + 20 + 22 + 24 = 94$。 题面翻译由 ChatGPT-4o 提供。