Description

米尔科在他的车后座上发现了一个有 $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$：

这样的矩阵对他来说不够有趣，所以他选择了一行或一列 $K$ 次，并将其值乘以一个非负整数。

自然地，现在他想知道矩阵中所有值的和。由于这个和可能非常大，米尔科将对其取模 $10^9 + 7$。帮助米尔科回答这个问题。

Input Format

输入的第一行包含任务中的数字 $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$）。

Output Format

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

3 4 4
R 2 4
S 4 1
R 3 2
R 2 0

94

3 1 1
S 1 4

24

2 4 4
S 2 0
S 2 3
R 1 5
S 1 3

80

Hint

在总共价值 $50$ 分的测试用例中，将满足 $1 \le N, M \le 10^3$。

第一个测试用例的说明：在将第二行乘以 $4$，第四列乘以 $1$，第三行乘以 $2$，再次将第二行乘以 $0$ 之后，最终矩阵如下所示：

最终矩阵中元素的和为 $1 + 2 + 3 + 4 + 0 + 0 + 0 + 0 + 18 + 20 + 22 + 24 = 94$。

题面翻译由 ChatGPT-4o 提供。