Mirko je na zadnjem sjedištu svog auta pronašao matricu s \(N\) redaka i \(M\) stupaca. U prvom retku matrice redom se nalaze brojevi \(1, 2, \ldots, M\), u drugom redom \(M+1, M+2, \ldots, 2M\) i tako sve od \(N\)-tog retka u kojem su redom \((N-1)⋅M + 1, (N-1)⋅M + 2, \ldots, NM\).

Npr. za \(N = 3\) i \(M = 4\):

Takva matrica nije mu bila dovoljno zanimljiva pa je \(K\) puta odabrao neki redak ili stupac te njegove vrijednosti pomnožio nekim nenegativnim cijelim brojem.

Sada ga, naravno, zanima zbroj svih vrijednosti u matrici. Budući da taj zbroj može biti jako velik Mirko će se zadovoljiti i s njegovim ostatkom pri dijeljenju s \(10^9 + 7\). Pomozite Mirku odgovoriti na ovo pitanje.

Ulazni podaci

U prvom retku nalaze se prirodni brojevi \(N\) \((1 \leq N \leq 1 000 000)\), \(M\) \((1 \leq M \leq 1 000 000)\) i \(K\) \((1 \leq K \leq 1000)\) iz teksta zadatka.

Slijedi \(K\) redaka od kojih svaki opisuje:

• ili množenje \(X\)-tog retka brojem \(Y\), oblika R X Y, pri čemu slovo \(R\) predstavlja množenje retka, \(X\) je prirodan broj \((1 \leq X \leq N)\), a \(Y\) nenegativan cijeli broj \((0 \leq Y \leq 10^9)\).

• ili množenje \(X\)-tog stupca brojem \(Y\), oblika S X Y, pri čemu slovo \(S\) predstavlja množenje stupca, \(X\) je prirodan broj \((1 \leq X \leq M)\), a \(Y\) nenegativan cijeli broj \((0 \leq Y \leq 10^9)\).

Izlazni podaci

U jedini redak ispišite ostatak zbroja završnih vrijednosti matrice pri dijeljenju s \(10^9 + 7\).

Bodovanje

U test podacima ukupno vrijednima 50 bodova vrijedit će \(1 \leq N, M \leq 1000\).

Primjeri test podataka

Ulaz

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

Izlaz

94

Objašnjenje

Nakon što drugi redak pomnožimo s \(4\), četvrti stupac s \(1\), treći redak s \(2\) i ponovo drugi redak s \(0\) završna matrica izgleda ovako:

Zbroj elemenata završne matrice je \(1 + 2 + 3 + 4 + 0 + 0 + 0 + 0 + 18 + 20 + 22 + 24 = 94\).

Ulaz

3 1 1
S 1 4

Izlaz

24

Ulaz

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

Izlaz

80