Automobil

Ο Μίρκο βρήκε ένας πίνακας με Ν σειρές και στήλες M στο πίσω κάθισμα του αυτοκινήτου του. Η πρώτη σειρά του πίνακα αποτελείται από τους αριθμούς 1, 2, ... , ~M~, η δεύτερη σειρά αριθμών ~M+1~, ~M+2~, ... , \(2⋅M\) και ούτω καθεξής μέχρι την ~N~-οστή σειρά που αποτελείται από αριθμούς \((N-1)⋅M + 1\), \((N​-1)⋅​M + 2\), ... , \(N⋅Μ\) αντίστοιχα.

Για παράδειγμα, για ~N~ = 3 και ~M~ = 4:

Ένας τέτοιος πίνακας δεν ήταν αρκετά ενδιαφέρον γι' αυτόν, γι' αυτό διάλεξε μια σειρά ή μια στήλη K φορές και πολλαπλασίασε τις τιμές της με έναν μη αρνητικό ακέραιο.

Φυσικά, τώρα θέλει να μάθει το άθροισμα όλων των τιμών από τον πίνακα.Επειδή αυτό το άθροισμα μπορεί να είναι πολύ μεγάλο, ο Mirko θα είναι ικανοποιημένος με την τιμή με τη μορφή υπολοίπου ακέραιας διαίρεσης με ~10^9 + 7~. Βοηθήστε τον Mirko να απαντήσει σε αυτήν την ερώτηση.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει τους αριθμούς ~N\; (1 \le N \le 1.000.000)~, ~M\;(1 \le M \le 1.000.000)~ και ~K\; (1 \le K \le 1.000)~ από την εργασία. Κάθε μία από τις ακόλουθες γραμμές ~K~ περιγράφει:
● Είτε τον πολλαπλασιασμό της ~X~-οστής σειράς με ~Y~ , με τη μορφή «~R\; X\; Y~», όπου το «~R~» αντιπροσωπεύει τον πολλαπλασιασμό σειράς, ~X~ είναι θετικός ακέραιος αριθμός ~(1 \le X \le N)~, και το ~Y~ είναι ένας μη αρνητικός ακέραιος αριθμός ~(0 \le Y \le 10^9)~.
●Eίτε τον πολλαπλασιασμό της ~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 1.000~.

Παραδείγματα

input

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

output

94

Επεξήγηση του 1ου παραδείγματος:

Μετά τον πολλαπλασιασμό της δεύτερης σειράς με 4, της τέταρτης στήλης με 1, της τρίτης σειράς με 2 και ξανά της δεύτερης σειράς με 0, ο τελικός πίνακας μοιάζει με αυτό:

Το άθροισμα των στοιχείων από τον τελικό πίνακα είναι ~1 + 2 + 3 + 4 + 0 + 0 + 0 + 0 + 18 + 20 + 22 + 24 = 94~.

input

3 1 1
S 1 4

output

24

input

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

output

80