题目描述

Mirko has found a matrix with N rows and M columns at the back seat of his car. The first row of the matrix consists of numbers 1, 2, … M, the second row of numbers M+1, M+2, … 2⋅M and so on until the $N^{th}$
row which consists of numbers (N-1)⋅M + 1, (N-1)⋅M + 2, … N⋅M, respectively.

For example, for N = 3 and M = 4:

Such matrix wasn’t interesting enough to him, so he chose a row or a column K times and multiplied its values with a non-negative integer.

Naturally, now he wants to know the sum of all the values from the matrix. Since this sum can be very large, Mirko will be satisfied with the value modulo $10^9$ + 7. Help Mirko answer this question.

输入格式

The first line of input contains the numbers N (1 ≤ N ≤ 1 000 000), M (1 ≤ M ≤ 1 000 000) and K (1 ≤ K ≤ 1000) from the task.

• Either the multiplication of the $X^{th}$ row with Y, in the form of "R X Y", where “R” represents row multiplication, X is a positive integer (1 ≤ X ≤ N), and Y is a non-negative integer (0 ≤ Y ≤ $10^{9}$ ).

• Or the multiplication of the $X^{th}$ column with Y, in the form of “S X Y”, where “S” represents column multiplication, X is a positive integer (1 ≤ X ≤ M), and Y is a non-negative integer (0 ≤ Y ≤ $10^{9}$ ).

输出格式

You must output the sum of the final values from the matrix modulo $10^{9}$ + 7

题目翻译

Mirko在汽车后座找到了一个N行M列的矩形，矩形第一行由数字1，2,3，…，M，第二行由M+1，M+2,…,2M组成，一直到第N行数字，由(N-1)*M+1, (N-1)M+2,…, NM组成。

举个例子，对于N=3，M=4的矩形，有：

由于这样的矩形不够有趣，于是他进行K次选择，每次选择一行或者一列，将这一行或一列上的所有值乘以一个非负整数。

K次操作完成后，Mirko想知道这个矩形中所有值的总和是多少。由于这个数字可能会非常大，答案将对1e9+7取模。

输入格式

第一行输入三个正整数N（1≤N≤1000000）,M(1≤M≤1000000)和K(1≤K≤1000)，表示矩形的大小和操作的次数。

接下来K行，每行包含三个字符。如果将第X行的所有值乘以Y，那么输入“R X Y”，如果将第X列的所有值乘以Y，那么输入“S X Y”。

输出格式

输出矩形中所有值的和对1e9+7取模的值。

样例 #1

样例输入 #1

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

样例输出 #1

94

样例 #2

样例输入 #2

3 1 1
S 1 4

样例输出 #2

24

样例 #3

样例输入 #3

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

样例输出 #3

80

提示

In test cases worth a total of 50 points, it will hold 1 ≤ N, M ≤ 1000.

Clarification of the first test case:

对于第一组样例，完成四次操作后，矩阵情况如下：

After multiplying the second row with 4, the fourth column with 1, the third row with 2, and again the second row with 0, the final matrix looks like this:

The sum of the elements from the final matrix is 1 + 2 + 3 + 4 + 0 + 0 + 0 + 0 + 18 + 20 + 22 + 24 = 94.