Matrix Multiplication Queries

Mirko has found a matrix with N rows and M columns in the back seat of his car. The matrix is constructed as follows: the first row consists of numbers 1, 2, …, M; the second row contains numbers M+1, M+2, …, 2⋅M; and so on until the N^th row which consists of numbers \((N-1)\times M + 1\), \((N-1)\times M + 2\), …, \(N\times M\).

For example, for N = 3 and M = 4, the matrix is:

Not satisfied with its appearance, Mirko performs K operations. In each operation, he selects either a row or a column and multiplies every value in that row or column by a non-negative integer. Note that if a cell is affected by both a row operation and a column operation, the multipliers multiply together.

The final task is to compute the sum of all the values in the matrix modulo \(10^9+7\). Formally, if the initial value at cell \((i,j)\) (with 1-based indices) is \((i-1)\times M + j\) and if after all operations the multiplier for row \(i\) is \(r_i\) and for column \(j\) is \(c_j\), then the final value at cell \((i,j)\) is:

\(((i-1)\times M + j) \times r_i \times c_j\)

Your task is to compute the sum:

\(\sum_{i=1}^{N} \sum_{j=1}^{M} \left(((i-1)\times M + j) \times r_i \times c_j\right)\)

and output it modulo \(10^9+7\).

inputFormat

The first line contains three integers N, M and K — the number of rows, columns, and the number of operations respectively.

Each of the next K lines contains an operation in one of the following formats:

• R r x: Multiply all numbers in row r (1-indexed) by x.
• C c x: Multiply all numbers in column c (1-indexed) by x.

Here, x is a non-negative integer.

outputFormat

Output a single integer — the sum of all the values in the matrix after performing all operations, taken modulo \(10^9+7\).

sample

3 4 2
R 2 2
C 3 3

160