Chef is here with another matrix A having N rows and M columns,  
such that A_{(i,j)} = (i-1)\cdot M+j. 

Chef decided to make this matrix interesting. He performed K operations on the matrix. In each operation, he will choose either a row or column and multiply all values in that row/column with a non-negative integer V.

An operation is of the form  Q, X, V:
- If Q=0: Multiply each element of the X^{th} row with V.
- If Q=1: Multiply each element of the X^{th} column with V.

Find the sum of all values in the matrix after all K operations are done. Since the value can be large, print it modulo 10^{9} + 7.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains three space-separated integers N, M, and K — the number of rows, columns, and the operations to be done, respectively.
- The next K lines describe the operations. The i^{th} of these K lines contain three space-separated integers Q_{i}, X_{i}, and V_{i}, as mentioned in the statement.

------ Output Format ------ 

For each test case, output on a new line, the sum of all elements of the matrix after performing the operations, modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 10^{9}$
$1 ≤ K ≤ 2\cdot 10^{5}$
$0 ≤ Q_{i} ≤ 1$ 
$1 ≤ X ≤ N$ if $Q_{i}=0$
$1 ≤ X ≤ M$ if $Q_{i}=1$ 
$0 ≤ V_{i} ≤ 10^{9}$ 
- The sum of $K$ over all test cases won't exceed $2\cdot 10^{5}$

----- Sample Input 1 ------ 
2
2 2 2
1 2 0
0 1 2
1 3 1
1 2 6
----- Sample Output 1 ------ 
5
16

----- explanation 1 ------ 
Test case $1$ : The initial matrix is $[[1, 2], [3, 4]]$.
- In the first operation, multiply all elements of the second column with $0$. Thus, the matrix becomes $[[1, 0], [3, 0]]$.
- In the second operation, multiply all elements of the first row with $2$. Thus, the matrix becomes $[[2, 0], [3, 0]]$.

The sum of the elements of the updated matrix is $2+3 = 5$.

Test case $2$: The initial matrix is $[[1, 2, 3]]$.
- In the first operation, multiply all elements of the second column with $6$. Thus, the matrix becomes $[[1, 12, 3]]$.

The sum of the elements of the updated matrix is $1+12+3 = 16$.

Difficulty: VERY_HARD
Tags: Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
mod = 10 ** 9 + 7

def calc(i, j):
	first = 0
	if i % 2 == 0:
		first = i // 2 * (i - 1)
	else:
		first = (i - 1) // 2 * i
	second = 0
	if j % 2 == 0:
		second = j // 2 * (j + 1)
	else:
		second = (j + 1) // 2 * j
	return (second - first) % mod
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	row = {}
	col = {}
	for _ in range(k):
		(q, x, v) = map(int, input().split())
		if q == 0:
			row[x] = row.get(x, 1) * v % mod
		else:
			col[x] = col.get(x, 1) * v % mod
	var = 0
	cons = 0
	sum = calc(1, n * m)
	for x in col:
		var = (var + col[x] - 1) % mod
		cons += (col[x] - 1) * x % mod
		cons %= mod
		val = (calc(0, n - 1) * m % mod + n * x % mod) % mod
		sum = (sum + val * (col[x] - 1) % mod) % mod
	var = var * m % mod
	for x in row:
		rowno = x
		rowc = row[x]
		sumr = calc((rowno - 1) * m + 1, rowno * m) + var * (rowno - 1) % mod + cons
		sumr %= mod
		add = sumr * (rowc - 1) % mod
		sum = (sum + add) % mod
	print(sum)


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split(' '))
	r = {}
	c = {}
	sum = m * n * (m * n + 1) // 2
	ra = rp = ca = cp = 0
	for j in range(k):
		(q, x, v) = map(int, input().split(' '))
		if q == 0:
			sum += (m * m * (x - 1) + m * (m + 1) // 2) * (v - 1)
			sum += (ra + rp * (x - 1)) * (v - 1)
			ca += m * (x - 1) * r.get(x, 1) * (v - 1)
			cp += r.get(x, 1) * (v - 1)
			r[x] = r.get(x, 1) * v
		else:
			sum += (m * n * (n - 1) // 2 + n * x) * (v - 1)
			sum += (ca + cp * x) * (v - 1)
			ra += x * c.get(x, 1) * (v - 1)
			rp += m * c.get(x, 1) * (v - 1)
			c[x] = c.get(x, 1) * v
	print(sum % 1000000007)


mod = pow(10, 9) + 7
t = int(input())
while t > 0:
	t = t - 1
	[n, m, k] = input().split()
	n = int(n)
	m = int(m)
	k = int(k)
	a = dict([])
	b = dict([])
	for _ in range(0, k):
		[q, x, v] = input().split()
		q = int(q)
		x = int(x)
		v = int(v)
		if q == 0:
			if x in a:
				a[x] *= v
				a[x] = a[x] % mod
			else:
				a[x] = v
		elif x in b:
			b[x] *= v
			b[x] = b[x] % mod
		else:
			b[x] = v
	s_a = n
	s_b = m
	for i in a:
		s_a += a[i] - 1
	for i in b:
		s_b += b[i] - 1
	w_a = (n * n + n) / 2
	w_b = (m * m + m) / 2
	w_a = int(w_a)
	w_b = int(w_b)
	w_a = w_a % mod
	w_b = w_b % mod
	for i in a:
		w_a += i * (a[i] - 1)
		w_a = w_a % mod
	for i in b:
		w_b += i * (b[i] - 1)
		w_b = w_b % mod
	print((m * w_a * s_b + s_a * w_b - m * s_a * s_b) % mod)


for _ in range(int(input())):
	mod = 1000000007
	(n, m, k) = [int(i) for i in input().split()]
	res = m * n * (m * n + 1) // 2
	q = []
	for t in range(k):
		q.append([int(i) for i in input().split()])
	q.sort()

	def sm(q, x, v):
		ans = 0
		if q == 0:
			ans = (v - 1) * ((x - 1) * m * m + m * (m + 1) // 2)
			return ans % mod
		ans = (v - 1) * (x * n + m * n * (n - 1) // 2)
		return ans % mod
	(jc, c, j) = (0, 0, 0)
	cnt = 0
	for t in range(k):
		if q[t][0] == 0:
			continue
		(_, jcurr, ccurr) = q[t]
		c += ccurr - 1
		j += jcurr
		jc += jcurr * ccurr
		cnt += 1

	def cross(r, R):
		return (m * (r - 1) * c + jc - j) * (R - 1) % mod
	for t in range(k):
		(_, jcurr, ccurr) = q[t]
		res += sm(*q[t])
	for t in range(k):
		if q[t][0] == 1:
			continue
		(_, jcurr, ccurr) = q[t]
		res += cross(jcurr, ccurr)
	print(res % mod)


mod = 1000000007

def calc(i, j):
	first = 0
	if i % 2 == 0:
		first = i // 2
		first = first % mod * ((i - 1) % mod) % mod
	else:
		first = (i - 1) // 2
		first = first % mod * (i % mod) % mod
	second = 0
	if j % 2 == 0:
		second = j // 2
		second = second % mod * ((j + 1) % mod) % mod
	else:
		second = (j + 1) // 2
		second = second % mod * (j % mod) % mod
	return (second - first + mod) % mod
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	row = {}
	col = {}
	while k > 0:
		k -= 1
		(q, x, v) = map(int, input().split())
		if q == 0:
			if x in row:
				row[x] = row[x] * v % mod
			else:
				row[x] = v
		elif x in col:
			col[x] = col[x] * v % mod
		else:
			col[x] = v
	var = 0
	cons = 0
	sum = calc(1, n * m)
	for x in col:
		var += col[x] - 1
		cons += (col[x] - 1) * x % mod
		var %= mod
		cons %= mod
		val = (calc(0, n - 1) * m % mod + n * x % mod) % mod
		sum = sum + val * (col[x] - 1) % mod
		sum = (sum + mod) % mod
	var = var * m % mod
	for x in row:
		rowno = x
		rowc = row[x]
		sumr = calc((rowno - 1) * m + 1, rowno * m) + var * (rowno - 1) % mod + cons
		sumr = sumr % mod
		add = sumr % mod * (rowc - 1) % mod % mod
		sum = sum + add
		sum = (sum + mod) % mod
	print(sum)


from collections import defaultdict
t = int(input())
M = 10 ** 9 + 7
for _ in range(t):
	(n, m, k) = map(int, input().split())
	rows = defaultdict(lambda : 1)
	cols = defaultdict(lambda : 1)
	for _ in range(k):
		(q, x, v) = map(int, input().split())
		if q == 0:
			rows[x] *= v
			rows[x] %= M
		if q == 1:
			cols[x] *= v
			cols[x] %= M
	currsum = 0
	colsum = m * (m + 1) // 2
	csum = m
	rowsum = n * (n + 1) // 2
	rsum = n
	for c in cols:
		colsum += c * (cols[c] - 1)
		csum += cols[c] - 1
		colsum %= M
		csum %= M
	for r in rows:
		rowsum += r * (rows[r] - 1)
		rsum += rows[r] - 1
		rowsum %= M
		rsum %= M
	currsum += (rowsum - rsum) * m * csum + rsum * colsum
	currsum %= M
	print(currsum)