COCI '17 Contest 4 #3 Automobil

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

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, \dots, M, the second row of numbers M+1, M+2, \dots, 2 \cdot M and so on until the N^\text{th} row which consists of numbers (N-1) \cdot M + 1, (N-1) \cdot M + 2, \dots, N \cdot M, respectively.

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

\displaystyle \begin{array}{|c|c|c|c|} \hline
1 & 2 & 3 & 4 \\ \hline
5 & 6 & 7 & 8 \\ \hline
9 & 10 & 11 & 12 \\ \hline \end{array}

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.

Input Specification

The first line of input contains the numbers N (1 \le N \le 1\,000\,000), M (1 \le M \le 1\,000\,000) and K (1 \le K \le 1000) from the task.
Each of the following K lines describes:

  • Either the multiplication of the X^\text{th} row with Y, in the form of "R X Y", where R represents row multiplication, X is a positive integer (1 \le X \le N), and Y is a non-negative integer (0 \le Y \le 10^9).
  • Or the multiplication of the X^\text{th} column with Y, in the form of "S X Y", where S represents column multiplication, X is a positive integer (1 \le X \le M), and Y is a non-negative integer (0 \le Y \le 10^9).

Output Specification

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

Scoring

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

Sample Input 1

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

Sample Output 1

94

Explanation for Sample Output 1

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:

\displaystyle \begin{array}{|c|c|c|c|} \hline
1 & 2 & 3 & 4 \\ \hline
0 & 0 & 0 & 0 \\ \hline
18 & 20 & 22 & 24 \\ \hline \end{array}

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

Sample Input 2

3 1 1
S 1 4

Sample Output 2

24

Sample Input 3

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

Sample Output 3

80

Comments

There are no comments at the moment.