Given a triplet of integers (X , Y , Z), such that X ≤ Y and Y ≥ Z, we define f(X , Y , Z) to be (X + Y) * (Y + Z). If either X > Y or Y < Z, or both, then f(X , Y , Z) is defined to be 0.
You are provided three arrays  A , B and C   of any length (their lengths may or may not be equal).  
Your task is to find the sum of f(X , Y , Z) over all triplets (X, Y , Z) where   X, Y and Z  belong to  A, B and C respectively.
Output your sum for each test case modulo 1000000007.

-----Input-----
- The first line contains a single integer, T, which is the number of test cases. The description of each testcase follows:
- The first line of each testcase contains 3 integers: p, q and r. These denote the lengths of A,B and C respectively. 
- The second line contains p integers, which are the elements of A
- The third line contains q integers, which are the elements of B
- The fourth line contains r integers, which are the elements of C

-----Output-----
Output the required sum modulo  1000000007  for each test case in a new line.

-----Constraints-----
- 1 ≤ T ≤ 10 
- 1 ≤ p, q, r ≤ 100000 
- 1 ≤ every array element ≤ 1000000000

-----Subtasks  -----
- Subtask #1 (30 points): 1 ≤ p,q,r  ≤ 100 
- Subtask #2 (70 points): 1 ≤ p,q,r  ≤ 100000 

-----Example : -----
Input:
1 
3 1 3
1 2 3
5
4 5 6

Output:
399

-----Explanation: -----
As there is only one choice for Y which equals to 5, to get a non-zero function value,we can choose any element for X from the set { 1 , 2 , 3 } and for Z from the set { 4  , 5 } 
So triplets which give non-zero function values are: 
{ 1 , 5  , 4 } :  ( 1 + 5 ) * ( 5 + 4 )  = 54 
{ 1 , 5  , 5 } :  ( 1 + 5 ) * ( 5 + 5 )  = 60 
{ 2 , 5  , 4 } :  ( 2 + 5 ) * ( 5 + 4 )  = 63 
{ 2 , 5  , 5 } :  ( 2 + 5 ) * ( 5 + 5 )  = 70 
{ 3 , 5  , 4 } :  ( 3 + 5 ) * ( 5 + 4 )  = 72 
{ 3 , 5  , 5 } :  ( 3 + 5 ) * ( 5 + 5 )  = 80 
Final answer : 54 + 60 + 63 + 70 + 72 + 80  = 399

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Range queries


Solutions:
counter = int(input())
for mrinal in range(counter):
	(x_size, y_size, z_size) = map(int, input().split())
	x = [int(i) for i in input().split()]
	y = [int(i) for i in input().split()]
	z = [int(i) for i in input().split()]
	x.sort()
	y.sort()
	z.sort()
	x_sum = []
	z_sum = []
	if y[y_size - 1] < x[0] or y[y_size - 1] < y[0]:
		print(0)
		continue
	count = 0
	for jithalel in x:
		count += jithalel
		x_sum.append(count)
	count = 0
	for bhide in z:
		count += bhide
		z_sum.append(count)
	y_counter = 0
	x_counter = 0
	z_counter = 0
	triplet_sum = 0
	while y_counter < y_size:
		while x_counter < x_size and x[x_counter] <= y[y_counter]:
			x_counter += 1
		while z_counter < z_size and z[z_counter] <= y[y_counter]:
			z_counter += 1
		if x_counter == 0 or z_counter == 0:
			y_counter += 1
			continue
		a = (x_sum[x_counter - 1] + x_counter * y[y_counter]) % 1000000007
		b = (z_sum[z_counter - 1] + z_counter * y[y_counter]) % 1000000007
		triplet_sum += a * b
		y_counter += 1
	print(triplet_sum % 1000000007)


m = 1000000007

def value(a, b, c):
	return (a + b) * (b + c) % m
t = int(input())
while t:
	t -= 1
	sum = 0
	(p, q, r) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	for i in b:
		a1 = [j for j in a if j <= i]
		c1 = [j for j in c if j <= i]
		for j in a1:
			for k in c1:
				sum = sum % m + value(j, i, k)
	print(sum % m)


t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	sum = 0
	(p, q, r) = map(int, input().split())
	a = sorted((int(x) for x in input().split()))
	b = sorted((int(x) for x in input().split()))
	c = sorted((int(x) for x in input().split()))
	t1 = t2 = sum1 = sum2 = 0
	for i in b:
		while t1 < p and a[t1] <= i:
			sum1 += a[t1]
			t1 += 1
		while t2 < r and c[t2] <= i:
			sum2 += c[t2]
			t2 += 1
		sum += (i * t1 + sum1) * (i * t2 + sum2)
	print(sum % mod)


mdl = 1000000007
for _ in range(int(input())):
	z = input().split()
	(p, q, r) = map(int, z[:3])
	z = input().split()
	a = list(map(int, z[:p]))
	z = input().split()
	b = list(map(int, z[:q]))
	z = input().split()
	c = list(map(int, z[:r]))
	a.sort()
	b.sort()
	c.sort()
	cta = ctc = 0
	suma = sumc = 0
	ans = 0
	for eb in b:
		while cta < p:
			if a[cta] > eb:
				break
			suma += a[cta]
			cta += 1
		while ctc < r:
			if c[ctc] > eb:
				break
			sumc += c[ctc]
			ctc += 1
		ans += suma * sumc + eb * (suma * ctc + cta * sumc + cta * ctc * eb)
		ans %= mdl
	print(ans)


from bisect import bisect
import time
import sys
MOD = 1000000007

def sum_list(a):
	r_list = []
	i = 0
	for a1 in a:
		if i == 0:
			r_list.append(a1)
		else:
			r_list.append(r_list[i - 1] + a1)
		i = i + 1
	return r_list

def func():
	(p, q, r) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	b = list(map(int, sys.stdin.readline().split()))
	c = list(map(int, sys.stdin.readline().split()))
	a.sort()
	c.sort()
	sum_a = sum_list(a)
	sum_c = sum_list(c)
	r_sum = 0
	for b1 in b:
		a_index = bisect(a, b1)
		c_index = bisect(c, b1)
		if not a_index or not c_index:
			r_sum += 0
			continue
		a_sum = sum_a[a_index - 1]
		c_sum = sum_c[c_index - 1]
		temp = (a_sum + a_index * b1 % MOD) % MOD * (c_sum + c_index * b1 % MOD) % MOD
		r_sum += temp % MOD
	return r_sum % MOD
T = int(input())
while T > 0:
	print(func())
	T = T - 1


T = int(input())
for a in range(T):
	(p, q, r) = map(int, input().split())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))
	C = sorted(list(map(int, input().split())))
	(i, j, k, l) = (0, 0, 0, 0)
	sum = 0
	for ele in B:
		while i < p and A[i] <= ele:
			k += A[i]
			i += 1
		while j < r and C[j] <= ele:
			l += C[j]
			j += 1
		sum += (i * ele + k) * (j * ele + l)
	print(sum % (10 ** 9 + 7))


m = 1000000007

def value(a, b, c):
	return (a + b) * (b + c) % m
t = int(input())
while t:
	t -= 1
	sum = 0
	(p, q, r) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	if min(a) > max(b) or max(b) < min(c):
		sum = 0
	else:
		for i in b:
			for j in a:
				for k in c:
					if j <= i and i >= k:
						sum = sum % m + value(j, i, k)
	print(sum % m)


T = int(input())
for i in range(T):
	n = list(map(int, input().split()))
	a = n[0]
	b = n[1]
	c = n[2]
	l = []
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = list(map(int, input().split()))
	for i in range(b):
		for j in range(a):
			for k in range(c):
				if A[j] <= B[i] and B[i] >= C[k]:
					sum = (A[j] + B[i]) * (B[i] + C[k])
					l.append(int(sum))
	sum = 0
	for i in range(len(l)):
		sum += int(l[i])
	print(sum % 1000000007)


t = int(input())
m = 1000000007
for i in range(t):
	(p, q, r) = map(int, input().split())
	pa = []
	qa = []
	ra = []
	pa.extend(map(int, input().split()))
	qa.extend(map(int, input().split()))
	ra.extend(map(int, input().split()))
	pa.sort(reverse=True)
	qa.sort(reverse=True)
	ra.sort(reverse=True)
	pas = [0]
	ras = [0]
	s = 0
	for j in range(p):
		s += pa[j]
		pas.append(s)
	s = 0
	for j in range(r):
		s += ra[j]
		ras.append(s)
	pind = 0
	rind = 0
	sm = 0
	for j in range(q):
		try:
			while pa[pind] > qa[j]:
				pind += 1
			while ra[rind] > qa[j]:
				rind += 1
		except:
			break
		sm = (sm + (pas[-1] - pas[pind] + (p - pind) * qa[j]) % m * ((ras[-1] - ras[rind] + (r - rind) * qa[j]) % m) % m) % m
	print(sm)


T = eval(input())
while T > 0:
	inp = input()
	a = inp.split()
	Alen = eval(a[0])
	Blen = eval(a[1])
	Clen = eval(a[2])
	A = list(map(int, input().split()))
	A.sort()
	B = list(map(int, input().split()))
	B.sort()
	C = list(map(int, input().split()))
	C.sort()
	y = 0
	sumfinal = 0
	Astart = 0
	Cstart = 0
	sumA = 0
	sumC = 0
	for i in range(0, Blen):
		sumy = 0
		y = B[i]
		j = Astart
		while j < Alen and A[j] <= y:
			x = A[j]
			sumA = sumA + x
			j = j + 1
		Astart = j
		k = Cstart
		while k < Clen and C[k] <= y:
			z = C[k]
			sumC = sumC + z
			k = k + 1
		Cstart = k
		sumy = (sumA + j * y) * (sumC + k * y)
		sumfinal = sumfinal + sumy
	print(sumfinal % 1000000007)
	T = T - 1


t = int(input())
modulo = 1000000007
for i in range(t):
	lens = input()
	lenlist = list(map(int, lens.split()))
	a1 = input()
	a = list(map(int, a1.split()))
	b1 = input()
	b = list(map(int, b1.split()))
	c1 = input()
	c = list(map(int, c1.split()))
	maxy = min(c)
	miny = min(a)
	b = [x for x in b if x >= maxy]
	b = [x for x in b if x >= miny]
	a.sort()
	b.sort()
	c.sort()
	alen = lenlist[0]
	blen = len(b)
	clen = lenlist[2]
	check = 0
	first = 0
	second = 0
	upsum = 0
	sum1 = 0
	sum2 = 0
	auxsum1 = 0
	mark1 = 0
	auxsum2 = 0
	mark2 = 0
	mach1 = 0
	mach2 = 0
	for yolo in range(blen):
		f = 'n'
		for q in range(mark1, alen):
			if b[yolo] < a[q]:
				f = 'y'
				mark1 = q
				break
			sum1 += a[q] % modulo
			first += 1
			mark1 = q
			if f == 'y':
				pass
			else:
				mark1 += 1
		mach1 = (sum1 % modulo + mark1 % modulo * b[yolo] % modulo % modulo) % modulo
		f = 'n'
		for q in range(mark2, clen):
			if b[yolo] < c[q]:
				f = 'y'
				break
			sum2 += c[q] % modulo
			second += 1
			mark2 = q
			if f == 'y':
				pass
			else:
				mark2 += 1
		mach2 = (sum2 % modulo + mark2 % modulo * b[yolo] % modulo % modulo) % modulo
		upsum += mach1 % modulo * mach2 % modulo % modulo
	print(upsum % modulo)


mod = 1000000007
for i in range(int(input())):
	(p, q, r) = map(int, input().split())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))
	C = sorted(list(map(int, input().split())))
	ans = 0
	k = 0
	l = 0
	s1 = 0
	c1 = 0
	s2 = 0
	c2 = 0
	for j in B:
		while k < p and A[k] <= j:
			s1 += A[k]
			c1 += 1
			k += 1
		while l < r and C[l] <= j:
			s2 += C[l]
			c2 += 1
			l += 1
		ans += s1 * s2 + c2 * s1 * j + c1 * s2 * j + c1 * c2 * j * j
	print(ans % mod)


from bisect import bisect_right
t = eval(input())
for i in range(t):
	s1 = []
	s2 = []
	s = list(map(int, input().split()))
	arr1 = list(map(int, input().split()))
	arr1.sort()
	v1 = arr1[0]
	s1.append(v1)
	for j in range(s[0] - 1):
		v1 = v1 + arr1[j + 1]
		s1.append(v1)
	arr2 = list(map(int, input().split()))
	arr3 = list(map(int, input().split()))
	arr2.sort()
	arr2.reverse()
	arr3.sort()
	v2 = arr3[0]
	s2.append(v2)
	for j in range(s[2] - 1):
		v2 = v2 + arr3[j + 1]
		s2.append(v2)
	v1 = 0
	for k in range(s[1]):
		a1 = bisect_right(arr1, arr2[k])
		a2 = bisect_right(arr3, arr2[k])
		if a1 != 0 and a2 != 0:
			v1 = (v1 + (s2[a2 - 1] + arr2[k] * a2) * (s1[a1 - 1] + arr2[k] * a1) % (10 ** 9 + 7)) % (10 ** 9 + 7)
		else:
			break
	print(v1)


for _ in range(int(input())):
	(u, v, w) = map(int, input().split())
	A1 = sorted(list(map(int, input().split())))
	B1 = sorted(list(map(int, input().split())))
	C1 = sorted(list(map(int, input().split())))
	(i, j, k, l) = (0, 0, 0, 0)
	sum = 0
	for item in B1:
		while i < u and A1[i] <= item:
			k += A1[i]
			i += 1
		while j < w and C1[j] <= item:
			l += C1[j]
			j += 1
		sum += (i * item + k) * (j * item + l)
	print(sum % (10 ** 9 + 7))


t = int(input())
for i in range(t):
	(n, m, p) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	c = sorted(list(map(int, input().split())))
	ans = 0
	mod = 1000000007
	(a1, b1, c1, d1) = (0, 0, 0, 0)
	for j in b:
		while a1 < n and a[a1] <= j:
			c1 += a[a1]
			a1 += 1
		while b1 < p and c[b1] <= j:
			d1 += c[b1]
			b1 += 1
		ans += (a1 * j + c1) * (b1 * j + d1)
	print(ans % mod)


t = int(input())
while t:
	(p, q, r) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	a.append(1000000000000)
	c.append(1000000000000)
	a.sort()
	b.sort()
	c.sort()
	sumx = [a[0]]
	sumz = [c[0]]
	x = 0
	for i in range(1, p):
		sumx.append(sumx[x] + a[i])
		x += 1
	x = 0
	for i in range(1, r):
		sumz.append(sumz[x] + c[i])
		x += 1
	nx = 0
	nz = 0
	x = 0
	for i in range(q):
		while a[nx] <= b[i]:
			nx += 1
		while c[nz] <= b[i]:
			nz += 1
		if nx and nz:
			x = x + nx * nz * b[i] * b[i] + sumx[nx - 1] * sumz[nz - 1] + (nz * sumx[nx - 1] + nx * sumz[nz - 1]) * b[i]
	print(x % 1000000007)
	sumx.clear()
	sumz.clear()
	t -= 1


t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	(p, q, r) = map(int, input().split())
	A = sorted((int(x) for x in input().split()))
	B = sorted((int(x) for x in input().split()))
	C = sorted((int(x) for x in input().split()))
	m = n = a = b = ans = 0
	for Y in B:
		while m < p and A[m] <= Y:
			a += A[m]
			m += 1
		while n < r and C[n] <= Y:
			b += C[n]
			n += 1
		ans += (Y * m + a) * (Y * n + b)
		ans %= mod
	print(ans)


t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	(p, q, r) = map(int, input().strip().split())
	a = sorted((int(x) for x in input().split()))
	b = sorted((int(x) for x in input().split()))
	c = sorted((int(x) for x in input().split()))
	ans = 0
	m = 0
	n = 0
	sum1 = 0
	sum2 = 0
	for i in b:
		while m < p and a[m] <= i:
			sum1 += a[m]
			m += 1
		while n < r and c[n] <= i:
			sum2 += c[n]
			n += 1
		ans += (sum1 + m * i) * (sum2 + n * i)
	print(ans % mod)


from itertools import groupby
t = int(input())
for test in range(t):
	(p, q, r) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	tmpB = list(map(int, input().split()))
	tmpB.sort()
	C = list(map(int, input().split()))
	C.sort()
	B = []
	freqB = []
	for (key, group) in groupby(tmpB):
		B.append(key)
		freqB.append(len(list(group)))
	q = len(B)
	sumA = [0]
	sumC = [0]
	ans = 0
	index = 0
	for j in A:
		sumA.append((j + sumA[index]) % 1000000007)
		index += 1
	index = 0
	for j in C:
		sumC.append((j + sumC[index]) % 1000000007)
		index += 1
	someMax = max(A[-1], C[-1])
	for i in range(q):
		query = B[i]
		if query >= someMax:
			while i < q:
				ans = (ans + (sumA[p] + B[i] * p % 1000000007) % 1000000007 * ((sumC[r] + B[i] * r % 1000000007) % 1000000007) % 1000000007 * freqB[i]) % 1000000007 % 1000000007
				i += 1
			break
		if query >= A[-1]:
			tmpA = (sumA[p] + query * p % 1000000007) % 1000000007
		else:
			low = 0
			high = p - 1
			while low <= high:
				mid = low + high >> 1
				if A[mid] <= query:
					low = mid + 1
				else:
					high = mid - 1
			if not low:
				continue
			tmpA = (sumA[low] + query * low % 1000000007) % 1000000007
		if query >= C[-1]:
			tmpC = (sumC[r] + query * r % 1000000007) % 1000000007
		else:
			low = 0
			high = r - 1
			while low <= high:
				mid = low + high >> 1
				if C[mid] <= query:
					low = mid + 1
				else:
					high = mid - 1
			if not low:
				continue
			tmpC = (sumC[low] + query * low % 1000000007) % 1000000007
		ans = (ans + tmpA * tmpC % 1000000007 * freqB[i] % 1000000007) % 1000000007
	print(ans)


m = 1000000007

def tripet(l1, l2, l3, n1, n2, n3):
	a = 0
	b = 0
	s = 0
	r = 0
	res = 0
	for i in l2:
		while a < n1 and l1[a] <= i:
			s += l1[a]
			a += 1
		while b < n3 and l3[b] <= i:
			r += l3[b]
			b += 1
		res += (i * a + s) * (i * b + r)
		res = res % m
	print(res)
for _ in range(int(input())):
	(n1, n2, n3) = map(int, input().split())
	l1 = sorted(list(map(int, input().strip().split())))
	l2 = sorted(list(map(int, input().strip().split())))
	l3 = sorted(list(map(int, input().strip().split())))
	tripet(l1, l2, l3, n1, n2, n3)


t = int(input())
for i in range(t):
	sum1 = 0
	sum2 = 0
	n = list(map(int, input().split()))
	p = n[0]
	q = n[1]
	r = n[2]
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr3 = list(map(int, input().split()))
	sum1 = sum(arr1)
	sum2 = sum(arr3)
	arr1.sort()
	arr2.sort()
	arr3.sort()
	flag = q - 1
	sumq = 0
	temp1 = p - 1
	temp2 = r - 1
	while flag >= 0:
		while temp1 >= 0 and arr1[temp1] > arr2[flag]:
			sum1 = sum1 - arr1[temp1]
			temp1 = temp1 - 1
		while temp2 >= 0 and arr3[temp2] > arr2[flag]:
			sum2 = sum2 - arr3[temp2]
			temp2 = temp2 - 1
		if temp1 == -1 or temp2 == -1:
			flag = -1
		else:
			sum1 = sum1 % 1000000007
			g = (temp1 + 1) * (arr2[flag] % 1000000007) % 1000000007
			h = (temp2 + 1) * (arr2[flag] % 1000000007) % 1000000007
			sumq = sumq + (sum1 + g) * (sum2 + h)
			sumq = sumq % 1000000007
			flag = flag - 1
	print(sumq)


T = int(input())
for _ in range(T):
	(p, q, r) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	c = sorted(list(map(int, input().split())))
	(i, j, m, n) = (0, 0, 0, 0)
	sm = 0
	for element in b:
		while i < p and a[i] <= element:
			m += a[i]
			i += 1
		while j < r and c[j] <= element:
			n += c[j]
			j += 1
		sm += (i * element + m) * (j * element + n)
	print(sm % (10 ** 9 + 7))


for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	a1 = list(map(int, input().split()))
	a2 = list(map(int, input().split()))
	a3 = list(map(int, input().split()))
	a1.sort()
	a2.sort()
	a3.sort()
	(a, b, c, d, sum) = (0, 0, 0, 0, 0)
	m = 10 ** 9 + 7
	for i in a2:
		while a < p and a1[a] <= i:
			c += a1[a]
			a += 1
		while b < r and a3[b] <= i:
			d += a3[b]
			b += 1
		sum += (i * a + c) * (i * b + d)
		sum %= m
	print(sum)


def R():
	return list(map(int, input().split()))
m = 1000000007
for i in range(int(input())):
	(a, b, c) = R()
	a1 = sorted(R())
	b1 = sorted(R())
	c1 = sorted(R())
	ass = css = asum = csum = s = 0
	for i in b1:
		while ass < a and a1[ass] <= i:
			asum += a1[ass]
			ass += 1
		while css < c and c1[css] <= i:
			csum += c1[css]
			css += 1
		s += (i * ass + asum) * (i * css + csum)
		s = s % m
	print(s)


for vaish in range(int(input())):
	(u_31809, v_31809, w_31809) = map(int, input().split())
	A1_31809 = sorted(list(map(int, input().split())))
	B1_31809 = sorted(list(map(int, input().split())))
	C1_31809 = sorted(list(map(int, input().split())))
	(i, j, k, l) = (0, 0, 0, 0)
	sum = 0
	for ele in B1_31809:
		while i < u_31809 and A1_31809[i] <= ele:
			k += A1_31809[i]
			i += 1
		while j < w_31809 and C1_31809[j] <= ele:
			l += C1_31809[j]
			j += 1
		sum += (i * ele + k) * (j * ele + l)
	print(sum % (10 ** 9 + 7))


testcases = int(input())
while testcases > 0:
	array_length = list(map(int, input().split()))
	array1 = list(map(int, input().split()))
	array2 = list(map(int, input().split()))
	array3 = list(map(int, input().split()))
	sum = 0
	for i in range(array_length[0]):
		for j in range(array_length[1]):
			for k in range(array_length[2]):
				if array1[i] <= array2[j] and array2[j] >= array3[k]:
					sum = (sum + (array1[i] + array2[j]) % 1000000007 * ((array2[j] + array3[k]) % 1000000007)) % 1000000007
	testcases -= 1
	print(sum % 1000000007)


import bisect

def main(args):
	t = int(input())
	while t > 0:
		(p, q, r) = map(int, input().split())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		c = list(map(int, input().split()))
		a.sort()
		b.sort()
		c.sort()
		a_sum = cum_sum(a, p)
		c_sum = cum_sum(c, r)
		sum_ = 0
		for i in b:
			p_ = bisect.bisect(a, i)
			r_ = bisect.bisect(c, i)
			if p_ > 0 and r_ > 0:
				sum_ = (sum_ + p_ * r_ * i * i + i * (r_ * a_sum[p_ - 1] + p_ * c_sum[r_ - 1]) + a_sum[p_ - 1] * c_sum[r_ - 1]) % (10 ** 9 + 7)
		print(sum_)
		t -= 1

def cum_sum(arr, n):
	sum_arr = [0] * n
	sum_arr[0] = arr[0]
	for i in range(1, n):
		sum_arr[i] = sum_arr[i - 1] + arr[i]
	return sum_arr
import sys
sys.exit(main(sys.argv))


from bisect import bisect_right as index
tests = int(input())
for x in range(tests):
	s = list(map(int, input().split()))
	anrml = list(map(int, input().split()))
	bnrml = list(map(int, input().split()))
	cnrml = list(map(int, input().split()))
	anrml.sort()
	cnrml.sort()
	suma = []
	sumc = []
	temp = 0
	for p in range(s[0]):
		temp = temp + anrml[p]
		suma.append(temp)
	temp = 0
	final = 0
	for q in range(s[2]):
		temp = temp + cnrml[q]
		sumc.append(temp)
	for r in range(s[1]):
		ind1 = index(anrml, bnrml[r]) - 1
		ind2 = index(cnrml, bnrml[r]) - 1
		if ind1 >= 0 and ind2 >= 0:
			final = (final + (suma[ind1] + bnrml[r] * (ind1 + 1)) * (sumc[ind2] + bnrml[r] * (ind2 + 1)) % (10 ** 9 + 7)) % (10 ** 9 + 7)
		else:
			continue
	print(final)


T = int(input().strip())
for test in range(T):
	mod = 1000000007
	(p, q, r) = input().strip().split(' ')
	(p, q, r) = (int(p), int(q), int(r))
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	C = [int(x) for x in input().split()]
	A.sort()
	B.sort()
	C.sort()
	sumofx = []
	countofx = []
	sumofz = []
	countofz = []
	(ans, i, summ) = (0, 0, 0)
	for y in B:
		while i < p and A[i] <= y:
			summ += A[i]
			i += 1
		countofx.append(i)
		sumofx.append(summ)
	i = 0
	summ = 0
	for y in B:
		while i < r and C[i] <= y:
			summ += C[i]
			i += 1
		countofz.append(i)
		sumofz.append(summ)
	for i in range(q):
		ans += (B[i] * B[i] % mod * countofx[i] % mod * countofz[i] % mod % mod + B[i] * countofz[i] % mod * sumofx[i] % mod % mod + B[i] * sumofz[i] % mod * countofx[i] % mod % mod + sumofz[i] * sumofx[i] % mod) % mod
	print(ans % mod)


def mod(n):
	return n % 1000000007
for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))
	C = sorted(list(map(int, input().split())))
	(ans, i, l) = (0, 0, 0)
	(sa, sc) = (0, 0)
	for b in B:
		while i < p and A[i] <= b:
			sa = mod(sa + A[i])
			i += 1
		while l < r and C[l] <= b:
			sc = mod(sc + C[l])
			l += 1
		if l > 0 and i > 0:
			ans = mod(ans + mod(b * b * i * l) + mod(b * l * sa) + mod(b * i * sc) + mod(sa * sc))
	print(ans)


import bisect
Mod = 1000000007
for _ in range(int(input())):
	_ = input()
	X = [int(i) for i in input().split()]
	Y = [int(i) for i in input().split()]
	Z = [int(i) for i in input().split()]
	(X.sort(), Z.sort())
	(X_sum, Z_sum) = ([X[0]], [Z[0]])
	for i in range(1, len(X)):
		X_sum.append((X_sum[i - 1] + X[i]) % Mod)
	for i in range(1, len(Z)):
		Z_sum.append((Z_sum[i - 1] + Z[i]) % Mod)
	Ans = 0
	for e in Y:
		(pos1, pos2) = (bisect.bisect_right(X, e), bisect.bisect_right(Z, e))
		if pos1 > 0 and pos2 > 0:
			Temp = (e * pos1 + X_sum[pos1 - 1]) * (e * pos2 + Z_sum[pos2 - 1]) % Mod
			Ans = (Ans + Temp) % Mod
	print(Ans)


t = int(input())
for i in range(t):
	(x, y, z) = map(int, input().split())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	n = list(map(int, input().split()))
	s = 0
	for j in range(x):
		for k in range(y):
			for f in range(z):
				if l[j] <= m[k] and m[k] >= n[f]:
					s = s + (l[j] + m[k]) * (m[k] + n[f])
	print(s % 1000000007)


import bisect
T = int(input())
n = 1
while n <= T:
	(p, q, r) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = list(map(int, input().split()))
	ans = 0
	A1 = []
	C1 = []
	s = 0
	A.sort()
	B.sort()
	C.sort()
	for i in range(p):
		s += A[i]
		A1.append(s)
	s = 0
	for i in range(r):
		s += C[i]
		C1.append(s)
	for i in range(q):
		if A[0] > B[i]:
			x = -1
		elif A[p - 1] <= B[i]:
			x = p - 1
		else:
			x = bisect.bisect(A, B[i]) - 1
		if C[0] > B[i]:
			y = -1
		elif C[r - 1] <= B[i]:
			y = r - 1
		else:
			y = bisect.bisect(C, B[i]) - 1
		if x != -1 and y != -1:
			s = x
			u = y
			ans = ans + B[i] * (u + 1) * A1[s] + A1[s] * C1[u] + (u + 1) * (s + 1) * B[i] * B[i] + B[i] * (s + 1) * C1[u]
	ans = int(ans)
	print(ans % 1000000007)
	n += 1


for _ in range(int(input())):
	(lx, ly, lz) = [int(x) for x in input().split()]
	x = sorted((int(x) for x in input().split()))
	y = sorted((int(x) for x in input().split()))
	z = sorted((int(x) for x in input().split()))
	nx = nz = sx = sz = r = 0
	for yy in y:
		while nx < lx and x[nx] <= yy:
			sx += x[nx]
			nx += 1
		while nz < lz and z[nz] <= yy:
			sz += z[nz]
			nz += 1
		r = (r + (nx * yy + sx) * (nz * yy + sz)) % 1000000007
	print(r)


t = int(input())
x = []
for i in range(t):
	s1 = input().split()
	p = int(s1[0])
	q = int(s1[1])
	r = int(s1[2])
	suma = 0
	sumc = 0
	a = input().split()
	for j in range(p):
		a[j] = int(a[j])
		suma += a[j]
	b = input().split()
	for j in range(q):
		b[j] = int(b[j])
	c = input().split()
	for j in range(r):
		c[j] = int(c[j])
		sumc += c[j]
	a.sort()
	b.sort()
	c.sort()
	sum = 0
	ca = p - 1
	cc = r - 1
	for j in range(q - 1, -1, -1):
		while a[ca] > b[j] and ca >= 0:
			suma -= a[ca]
			ca -= 1
		while cc >= 0 and c[cc] > b[j]:
			sumc -= c[cc]
			cc -= 1
		if suma == 0 or sumc == 0:
			break
		sum += suma * sumc + b[j] ** 2 * (ca + 1) * (cc + 1) + (suma * (cc + 1) + sumc * (ca + 1)) * b[j]
	x.append(sum % 1000000007)
for i in range(t):
	print(x[i])


for ti in range(int(input())):
	(pn, qn, rn) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	q = list(map(int, input().split()))
	r = list(map(int, input().split()))
	p.sort()
	q.sort()
	r.sort()
	x = y = z = 0
	psum = rsum = 0
	tsum = 0
	for y in range(0, qn):
		while x < pn and p[x] <= q[y]:
			psum = psum + p[x]
			x = x + 1
		while z < rn and r[z] <= q[y]:
			rsum = rsum + r[z]
			z = z + 1
		if x > 0 and z > 0:
			tsum = (tsum + (psum + q[y] * x) * (q[y] * z + rsum)) % 1000000007
	print(tsum)


T = int(input())
for t in range(T):
	inp = input().split()
	P = int(inp[0])
	Q = int(inp[1])
	R = int(inp[2])
	A = input().split()
	A = list(map(int, A))
	A.sort()
	B = input().split()
	B = list(map(int, B))
	B.sort()
	C = input().split()
	C = list(map(int, C))
	C.sort()
	A_sum = []
	C_sum = []
	A_sum.append(0)
	C_sum.append(0)
	i = 0
	for a in A:
		A_sum.append(a + A_sum[i])
		i = i + 1
	j = 0
	for c in C:
		C_sum.append(c + C_sum[j])
		j = j + 1
	p_visited = 0
	r_visited = 0
	output = 0
	for q in B:
		while p_visited < P and A[p_visited] <= q:
			p_visited = p_visited + 1
		while r_visited < R and C[r_visited] <= q:
			r_visited = r_visited + 1
		if r_visited != 0 and p_visited != 0:
			output = output + (A_sum[p_visited] + p_visited * q) * (C_sum[r_visited] + r_visited * q)
	print(output % (10 ** 9 + 7))


M = 1000000007

def func(y, xsum, zsum, vx, vz):
	return y * ((xsum * vz % M + zsum * vx % M) % M) % M + vx * (vz * (y * y % M) % M) % M + xsum * zsum % M
t = int(input())
while t > 0:
	(p, q, r) = input().split()
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	p = int(p)
	q = int(q)
	r = int(r)
	a.sort()
	b.sort()
	c.sort()
	Sum = 0
	xsum = 0
	zsum = 0
	vx = 0
	vz = 0
	for i in range(0, q):
		for j in range(vx, p):
			if a[j] > b[i]:
				break
			vx += 1
			xsum = (xsum + a[j]) % M
		for j in range(vz, r):
			if c[j] > b[i]:
				break
			vz += 1
			zsum = (zsum + c[j]) % M
		Sum = (Sum + func(b[i], xsum, zsum, vx, vz)) % M
	print(Sum, '\n')
	t = t - 1


for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	ar1 = sorted(list(map(int, input().split())))
	ar2 = sorted(list(map(int, input().split())))
	ar3 = sorted(list(map(int, input().split())))
	a = b = c = d = 0
	n = 0
	mod = 10 ** 9 + 7
	for i in ar2:
		while a < p and ar1[a] <= i:
			c += ar1[a]
			a += 1
		while b < r and ar3[b] <= i:
			d += ar3[b]
			b += 1
		n += (i * a + c) * (i * b + d)
		n %= mod
	print(n)


import sys
t = int(input())
while t:
	(x, y, z) = map(int, sys.stdin.readline().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	count = 0
	a.sort()
	b.sort()
	c.sort()
	i = 0
	j = 0
	asum = 0
	csum = 0
	ans = 0
	for elm in b:
		if i < x:
			while elm >= a[i]:
				asum += a[i]
				i += 1
				if i >= x:
					break
		if j < z:
			while elm >= c[j]:
				csum += c[j]
				j += 1
				if j >= z:
					break
		if i != 0 and j != 0:
			ans += (asum + elm * i) * (csum + elm * j)
	print(ans % 1000000007)
	t -= 1


import copy
t = int(input())
for i in range(t):
	k = list(map(int, input().split()))
	len1 = copy.copy(k[0])
	len2 = copy.copy(k[2])
	m = list(map(int, input().split()))
	m.sort(reverse=True)
	suma = sum(m)
	n = list(map(int, input().split()))
	n.sort(reverse=True)
	o = list(map(int, input().split()))
	o.sort(reverse=True)
	sumb = sum(o)
	sum1 = 0
	start1 = 0
	start2 = 0
	for w in range(k[1]):
		sum2 = 0
		sum3 = 0
		for ui in range(start1, len1):
			if n[w] < m[ui]:
				suma = suma - m[ui]
				start1 = start1 + 1
			elif n[w] >= m[ui]:
				break
		sum2 = sum2 + (suma + (len1 - start1) * n[w])
		for uo in range(start2, len2):
			if n[w] < o[uo]:
				sumb = sumb - o[uo]
				start2 = start2 + 1
			elif n[w] >= o[uo]:
				break
		sum3 = sum3 + (sumb + (len2 - start2) * n[w])
		sum1 = sum1 + sum3 * sum2
	print(sum1 % 1000000007)


T = int(input())
while T > 0:
	T -= 1
	[p, q, r] = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = list(map(int, input().split()))
	A.sort()
	B.sort()
	C.sort()
	A_pos = 0
	A_sum = 0
	C_pos = 0
	C_sum = 0
	S = 0
	for i in range(q):
		for j in range(A_pos, p):
			if A[j] > B[i]:
				break
			A_sum += A[j]
			A_pos += 1
		for k in range(C_pos, r):
			if C[k] > B[i]:
				break
			C_sum += C[k]
			C_pos += 1
		S = (S + (A_pos * B[i] + A_sum) * (C_pos * B[i] + C_sum)) % 1000000007
	print(S)


T = int(input())
for _ in range(0, T):
	(x, y, z) = map(int, input().split())
	X = list(map(int, input().split()))
	Y = list(map(int, input().split()))
	Z = list(map(int, input().split()))
	x = x + 1
	z = z + 1
	X.insert(0, 0)
	Z.insert(0, 0)
	X.sort()
	Y.sort()
	Z.sort()
	sumx = list()
	sumx.append(0)
	for i in range(1, x):
		sumx.append(sumx[i - 1] + X[i])
	sumz = list()
	sumz.append(0)
	for i in range(1, z):
		sumz.append(sumz[i - 1] + Z[i])
	sum = 0
	px = 1
	py = 1
	pz = 1
	for i in range(y):
		while X[px] <= Y[i] and px <= x - 1:
			px = px + 1
			if px == x:
				break
		px = px - 1
		while Z[pz] <= Y[i] and pz <= z - 1:
			pz = pz + 1
			if pz == z:
				break
		pz = pz - 1
		sum += Y[i] * (px * pz * Y[i] + px * sumz[pz]) + sumx[px] * (pz * Y[i] + sumz[pz])
	print(sum % 1000000007)


t = int(input())
for i in range(0, t):
	(p, q, r) = map(int, input().split())
	x = [int(x) for x in input().split()]
	y = [int(x) for x in input().split()]
	z = [int(x) for x in input().split()]
	s = 0
	for j in range(0, p):
		for k in range(0, q):
			for l in range(0, r):
				if x[j] > y[k] or y[k] < z[l]:
					s += 0
				else:
					s += (x[j] + y[k]) * (y[k] + z[l])
	print(s % (10 ** 9 + 7))


def func(arr, key):
	low = 0
	high = len(arr)
	mid = -1
	flag = False
	while low < high:
		mid = (low + high) // 2
		if arr[mid] == key:
			flag = True
			break
		elif arr[mid] < key:
			low = mid + 1
		else:
			high = mid
	if flag:
		while mid < len(arr) and arr[mid] == key:
			mid = mid + 1
		mid = mid - 1
		return mid
	elif low >= len(arr):
		return len(arr) - 1
	elif low - 1 > len(arr) and arr[low - 1] > key:
		return -1
	else:
		return low - 1
T = int(input())
for i in range(T):
	mod = 1000000007
	(p, q, r) = map(int, input().split())
	parr = list(map(int, input().split()))
	qarr = list(map(int, input().split()))
	rarr = list(map(int, input().split()))
	parr.sort()
	rarr.sort()
	dicty = {}
	cumP = [0] * p
	cumR = [0] * r
	cumP[0] = parr[0]
	cumR[0] = rarr[0]
	maxp = parr[len(parr) - 1]
	maxr = rarr[len(rarr) - 1]
	for i in range(1, p):
		cumP[i] = cumP[i - 1] + parr[i]
	for i in range(1, r):
		cumR[i] = cumR[i - 1] + rarr[i]
	for j in range(len(qarr)):
		if qarr[j] in dicty:
			dicty[qarr[j]] = dicty[qarr[j]] + 1
		else:
			dicty[qarr[j]] = 1
	final = 0
	cy = 0
	temp = False
	for key in dicty:
		if key < cy and temp:
			continue
		if key >= maxp:
			nx = len(parr)
		else:
			nx = func(parr, key) + 1
		if key >= maxr:
			nz = len(rarr)
		else:
			nz = func(rarr, key) + 1
		if nx == 0 or nz == 0:
			cy = key
			temp = True
			continue
		sx = cumP[nx - 1]
		sz = cumR[nz - 1]
		con = sx * sz
		cp = nx * sz + nz * sx
		cp2 = nx * nz
		cp2 = cp2 * key ** 2
		cp = cp * key
		cp2 = cp2 % mod
		cp = cp % mod
		con = con % mod
		ans = (cp2 + cp + con) % mod
		final = (final + ans * dicty[key]) % mod
	print(final)


mod = 1000000007
t = int(input())
for j in range(t):
	(p, q, r) = input().split()
	p = int(p)
	q = int(q)
	r = int(r)
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	res = 0
	a.sort()
	b.sort()
	c.sort()
	prev_suma = 0
	prev_sumc = 0
	counta = 0
	countc = 0
	prev_i = 0
	indexa = 0
	indexc = 0
	for i in b:
		suma = (prev_suma + counta * (i - prev_i) % mod) % mod
		sumc = (prev_sumc + countc * (i - prev_i) % mod) % mod
		while indexa < p:
			if i >= a[indexa]:
				suma = (suma + (i + a[indexa]) % mod) % mod
				counta += 1
				indexa += 1
			else:
				break
		while indexc < r:
			if i >= c[indexc]:
				sumc = (sumc + (i + c[indexc]) % mod) % mod
				countc += 1
				indexc += 1
			else:
				break
		prev_i = i
		prev_suma = suma
		prev_sumc = sumc
		res = (res + suma * sumc % mod) % mod
	print(res)


z = 1000000007
for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = list(map(int, input().split()))
	A.sort()
	B.sort()
	C.sort()
	sA = [0] * p
	sB = [0] * q
	sC = [0] * r
	sA[0] = A[0]
	sB[0] = B[0]
	sC[0] = C[0]
	for i in range(1, p):
		sA[i] = (sA[i - 1] + A[i]) % z
	for i in range(1, q):
		sB[i] = (sB[i - 1] + B[i]) % z
	for i in range(1, r):
		sC[i] = (sC[i - 1] + C[i]) % z
	j = 0
	k = 0
	ans = 0
	for i in B:
		while j < p:
			if A[j] <= i:
				j += 1
			else:
				break
		while k < r:
			if C[k] <= i:
				k += 1
			else:
				break
		if A[j - 1] > i or C[k - 1] > i:
			continue
		ans = (ans + (j * i % z + sA[j - 1] % z) * (k * i % z + sC[k - 1] % z) % z) % z
	print(ans)


def solve(p, q, r, a, b, c):
	mod = 10 ** 9 + 7
	for i in range(len(b)):
		a.sort()
		b.sort()
		c.sort()
		m = 0
		n = 0
		sum1 = 0
		sum2 = 0
		count = 0
		for i in b:
			while m < p and a[m] <= i:
				sum1 += a[m]
				m += 1
			while n < r and c[n] <= i:
				sum2 += c[n]
				n += 1
			count += (sum1 + m * i) * (sum2 + n * i)
		return count % mod
test = int(input())
for _ in range(test):
	(p, q, r) = map(float, input().rstrip().split())
	a = list(map(int, input().rstrip().split()))
	b = list(map(int, input().rstrip().split()))
	c = list(map(int, input().rstrip().split()))
	print(solve(p, q, r, a, b, c))


t = int(input())
for i in range(t):
	(p, q, r) = map(int, input().split())
	a1 = sorted(list(map(int, input().split())))
	a2 = sorted(list(map(int, input().split())))
	a3 = sorted(list(map(int, input().split())))
	a = b = c = d = 0
	n = 0
	mod = 10 ** 9 + 7
	for i in a2:
		while a < p and a1[a] <= i:
			c += a1[a]
			a += 1
		while b < r and a3[b] <= i:
			d += a3[b]
			b += 1
		n += (i * a + c) * (i * b + d)
		n %= mod
	print(n)


import bisect
t = int(input())
MOD = 1000000007
for _ in range(t):
	(p, q, r) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	a.sort()
	c.sort()
	sum_a = []
	sum_c = []
	sum_a.append(a[0])
	sum_c.append(c[0])
	for i in range(1, p):
		sum_a.append((sum_a[i - 1] + a[i]) % MOD)
	for i in range(1, r):
		sum_c.append((sum_c[i - 1] + c[i]) % MOD)
	total = 0
	for i in range(q):
		inda = bisect.bisect_right(a, b[i])
		indc = bisect.bisect_right(c, b[i])
		suma = 0
		sumc = 0
		if inda > 0 and indc > 0:
			suma = (sum_a[inda - 1] + inda * b[i]) % MOD
			sumc = (sum_c[indc - 1] + indc * b[i]) % MOD
		total += suma * sumc
		total %= MOD
	print(total)


M = 1000000007

def solve():
	sum = 0
	(i, k) = (0, 0)
	(x_sum, z_sum) = (0, 0)
	for b in B:
		while i < p and A[i] <= b:
			x_sum = (x_sum + A[i]) % M
			i += 1
		while k < r and C[k] <= b:
			z_sum = (z_sum + C[k]) % M
			k += 1
		sum = (sum + (i * b % M + x_sum) % M * (k * b % M + z_sum) % M % M) % M
	return sum
T = int(input())
while T:
	(p, q, r) = map(int, input().split())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))
	C = sorted(list(map(int, input().split())))
	print(solve())
	T -= 1


import itertools
import bisect
times = int(input().strip(' '))
while times > 0:
	total = 0
	xy = 0
	(p, q, r) = map(int, input().strip(' ').split(' '))
	A = list(map(int, input().strip(' ').split(' ')))
	B = list(map(int, input().strip(' ').split(' ')))
	C = list(map(int, input().strip(' ').split(' ')))
	A.sort()
	C.sort()
	X = list(itertools.accumulate(A))
	Z = list(itertools.accumulate(C))
	for i in range(len(B)):
		i1 = bisect.bisect_right(A, B[i])
		i2 = bisect.bisect_right(C, B[i])
		if i1 == 0 or i2 == 0:
			continue
		total = (total + (i1 * B[i] + X[i1 - 1]) * (i2 * B[i] + Z[i2 - 1]) % 1000000007) % 1000000007
	print(total)
	times -= 1


for v in range(int(input())):
	(p, q, r) = input().split(' ')
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	a.sort()
	b.sort()
	d.sort()
	s = 0
	su = 0
	c = 0
	ss = 0
	cc = 0
	sum = 0
	susu = 0
	for w in range(int(q)):
		s = s + ss + b[w] * c
		while c < int(p):
			if a[c] <= b[w]:
				s = s + a[c] + b[w]
				ss = ss + a[c]
				c = c + 1
			else:
				break
		su = su + susu + b[w] * cc
		while cc < int(r):
			if d[cc] <= b[w]:
				su = su + d[cc] + b[w]
				susu = susu + d[cc]
				cc = cc + 1
			else:
				break
		sum = sum + s * su
		s = 0
		su = 0
	print(sum % 1000000007)


t = int(input())
for i in range(t):
	sumf = 0
	sumf1 = 0
	(p, q, r) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	c = list(map(int, input().split(' ')))
	a.sort()
	b.sort()
	c.sort()
	sum1 = 0
	sum2 = 0
	index1 = len(a) - 1
	index2 = len(c) - 1
	v = b[len(b) - 1]
	for g in range(len(a)):
		sum1 += a[g]
		if a[g] > v:
			sum1 -= a[g]
			index1 = g - 1
			break
	for g in range(len(c)):
		sum2 += c[g]
		if c[g] > v:
			sum2 -= c[g]
			index2 = g - 1
			break
	sumf += (sum1 + (index1 + 1) * v) * (sum2 + (index2 + 1) * v)
	if len(b) > 1:
		sum3 = 0
		sum4 = 0
		for h1 in range(len(b) - 2, -1, -1):
			flag1 = 0
			flag2 = 0
			for h in range(index1, -1, -1):
				sum3 += a[h]
				if a[h] <= b[h1]:
					sum3 -= a[h]
					flag1 = 1
					index1 = h
					break
			if flag1 == 1:
				for h in range(index2, -1, -1):
					sum4 += c[h]
					if c[h] <= b[h1]:
						sum4 -= c[h]
						flag2 = 1
						index2 = h
						break
			if flag1 == 1 and flag2 == 1:
				sumf1 = (sum1 - sum3 + (index1 + 1) * b[h1]) * (sum2 - sum4 + (index2 + 1) * b[h1])
			else:
				sumf1 = 0
			if sumf1 > 0:
				sumf += sumf1
			elif sumf1 == 0:
				break
		print(sumf % 1000000007)
	else:
		print(sumf % 1000000007)


import itertools
T = int(input())
for case in range(T):
	(p, q, r) = map(int, input().split())
	xs = list(map(int, input().split()))
	ys = list(map(int, input().split()))
	zs = list(map(int, input().split()))
	(xs.sort(), ys.sort(), zs.sort())
	(sumx, sumz, ix, iz) = (0, 0, 0, 0)
	ans = 0
	for (iy, y) in enumerate(ys):
		while ix < p and xs[ix] <= y:
			sumx = sumx + xs[ix]
			ix = ix + 1
		while iz < r and zs[iz] <= y:
			sumz = sumz + zs[iz]
			iz = iz + 1
		ans = ans + y * y * ix * iz + y * (sumx * iz + sumz * ix) + sumx * sumz
		ans = ans % 1000000007
	print(ans)


t = int(input())
for k in range(t):
	(p, q, r) = map(int, input().rstrip().split())
	l1 = sorted(list(map(int, input().rstrip().split())))
	l2 = sorted(list(map(int, input().rstrip().split())))
	l3 = sorted(list(map(int, input().rstrip().split())))
	(i, j, k, s, sum) = (0, 0, 0, 0, 0)
	for y in l2:
		while i < p and y >= l1[i]:
			k = k + l1[i]
			i = i + 1
		while j < r and y >= l3[j]:
			s = s + l3[j]
			j = j + 1
		sum = sum + (i * y + k) * (j * y + s)
	print(sum % (10 ** 9 + 7))


t = int(input())
for i in range(t):
	(p, q, r) = list(map(int, input().split()))
	a = list(sorted(list(map(int, input().split()))))
	b = list(sorted(list(map(int, input().split()))))
	c = list(sorted(list(map(int, input().split()))))
	la = lc = 0
	sa = sc = 0
	s = 0
	for y in b:
		while la < p and a[la] <= y:
			sa += a[la]
			la += 1
		while lc < r and c[lc] <= y:
			sc += c[lc]
			lc += 1
		s += (la * y + sa) * (lc * y + sc) % 1000000007
	print(s % 1000000007)


from bisect import bisect_right
t = int(input())
for _ in range(t):
	mod = 1000000007
	(p, q, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	a.sort()
	b.sort()
	c.sort()
	a_sum = [a[0]]
	for i in range(1, p):
		a_sum.append((a_sum[-1] + a[i]) % mod)
	c_sum = [c[0]]
	for i in range(1, r):
		c_sum.append((c_sum[-1] + c[i]) % mod)
	answer = 0
	for i in range(q):
		a_index = bisect_right(a, b[i])
		c_index = bisect_right(c, b[i])
		if a_index > 0 and c_index > 0:
			answer += a_index * c_index * b[i] * b[i]
			answer += b[i] * c_index * a_sum[a_index - 1]
			answer += b[i] * a_index * c_sum[c_index - 1]
			answer += a_sum[a_index - 1] * c_sum[c_index - 1]
			answer %= mod
	print(answer)


def findind(sizea, mini, lista):
	lo = 0
	hi = sizea
	mid = (lo + hi) // 2
	while lo < hi:
		mid = (lo + hi) // 2
		if lista[mid] > mini:
			hi = mid
		else:
			lo = mid + 1
	return lo

def findind1(sizea, mini, lista):
	lo = 0
	hi = sizea
	mid = (lo + hi) // 2
	while lo < hi:
		mid = (lo + hi) // 2
		if lista[mid] >= mini:
			hi = mid
		else:
			lo = mid + 1
	return lo
test = int(input())
for codechef in range(test):
	blah = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	a = sorted(a)
	b = sorted(b)
	c = sorted(c)
	sizea = blah[0]
	sizeb = blah[1]
	sizec = blah[2]
	j = b[-1]
	pos1 = findind(sizea, j, a)
	pos2 = findind(sizec, j, c)
	a = a[:pos1]
	c = c[:pos2]
	sizea = len(a)
	sizeb = len(b)
	sizec = len(c)
	if sizea == 0 or sizec == 0:
		print('0')
		continue
	mini1 = a[0]
	mini2 = c[0]
	if mini1 > mini2:
		posw = findind1(sizeb, mini1, b)
	else:
		posw = findind1(sizeb, mini2, b)
	b = b[posw:]
	sizea = len(a)
	sizeb = len(b)
	sizec = len(c)
	ans = 0
	prepos1 = -1
	prepos2 = -1
	sumarraya = []
	tem = 0
	for i in a:
		tem += i
		sumarraya.append(tem)
	tem = 0
	sumarrayc = []
	for i in c:
		tem += i
		sumarrayc.append(tem)
	jp = 0
	ansprev = 0
	prepos1 = 0
	prepos2 = 0
	(flaga, flagc) = (0, 0)
	for j in b:
		if j == jp:
			ans += ansprev
			continue
		if pos1 <= sizea - 1:
			if a[pos1] <= j:
				pos1 = findind(sizea, j, a)
		if flaga == 0 and pos1 >= sizea:
			pos1 = findind(sizea, j, a)
			flaga = 1
		if pos2 <= sizec - 1:
			if c[pos2] <= j:
				pos2 = findind(sizec, j, c)
		if flagc == 0 and pos2 >= sizec:
			pos2 = findind(sizec, j, c)
			flagc = 1
		if pos2 == 0 or pos1 == 0:
			jp = j
			continue
		ansprev = j * j * pos1 * pos2 % 1000000007 + j * (sumarraya[pos1 - 1] * pos2 + sumarrayc[pos2 - 1] * pos1) % 1000000007 + sumarraya[pos1 - 1] * sumarrayc[pos2 - 1] % 1000000007
		ans += ansprev
		jp = j
	print(ans % 1000000007)


t = int(input())
for i in range(t):
	[p, q, r] = [int(n) for n in input().split()]
	A = [int(n) for n in input().split()]
	B = [int(n) for n in input().split()]
	C = [int(n) for n in input().split()]
	A.sort()
	B.sort()
	C.sort()
	sumA = p * [0]
	sumB = q * [0]
	sumC = r * [0]
	sumA[0] = A[0]
	sumB[0] = B[0]
	sumC[0] = C[0]
	for i in range(1, q):
		sumB[i] = sumB[i - 1] + B[i]
	for i in range(1, p):
		sumA[i] = sumA[i - 1] + A[i]
	for i in range(1, r):
		sumC[i] = sumC[i - 1] + C[i]
	sum = 0
	yindex = 0
	xindex = 0
	zindex = 0
	while yindex < q:
		flag = True
		while xindex < p and B[yindex] >= A[xindex]:
			xindex = xindex + 1
			flag = False
		if not flag:
			xindex = xindex - 1
			flag = True
		while zindex < r and B[yindex] >= C[zindex]:
			zindex = zindex + 1
			flag = False
		if not flag:
			zindex = zindex - 1
		if B[yindex] >= A[xindex] and B[yindex] >= C[zindex]:
			sum = sum + B[yindex] * B[yindex] * (xindex + 1) * (zindex + 1) + B[yindex] * (sumA[xindex] * (zindex + 1) + sumC[zindex] * (xindex + 1)) + sumA[xindex] * sumC[zindex]
		yindex = yindex + 1
	print(sum % 1000000007)


import bisect as bi
t = int(input())
for i in range(t):
	array_pqr = list(map(int, input().rstrip().split(' ')))
	array_p = list(map(int, input().rstrip().split(' ')))
	array_q = list(map(int, input().rstrip().split(' ')))
	array_r = list(map(int, input().rstrip().split(' ')))
	array_p.sort()
	array_q.sort()
	array_r.sort()
	cumsum_p = [array_p[0]]
	cumsum_r = [array_r[0]]
	for j in range(1, array_pqr[0]):
		cumsum_p.append(cumsum_p[j - 1] + array_p[j])
	for j in range(1, array_pqr[2]):
		cumsum_r.append(cumsum_r[j - 1] + array_r[j])
	sum_answer = 0
	for j in range(array_pqr[1]):
		present_element = array_q[j]
		x_last = bi.bisect_right(a=array_p, x=present_element) - 1
		z_last = bi.bisect_right(a=array_r, x=present_element) - 1
		if x_last > -1 and z_last > -1:
			term1 = cumsum_p[x_last] + (x_last + 1) * present_element
			term2 = cumsum_r[z_last] + (z_last + 1) * present_element
			sum_answer += term1 * term2 % (10 ** 9 + 7)
			sum_answer %= 10 ** 9 + 7
	print(sum_answer)


ls1 = []
ls2 = []
ls3 = []
for x in range(int(input())):
	(p, q, r) = map(int, input().split())
	ls1 = list(map(int, input().split()))
	ls2 = list(map(int, input().split()))
	ls3 = list(map(int, input().split()))
	ls1.sort()
	ls2.sort()
	ls3.sort()
	ans = 0
	i = 0
	j = 0
	sum1 = 0
	sum2 = 0
	for a in range(q):
		if i < p:
			while ls2[a] >= ls1[i]:
				sum1 += ls1[i]
				i += 1
				if i >= p:
					break
		if j < r:
			while ls2[a] >= ls3[j]:
				sum2 += ls3[j]
				j += 1
				if j >= r:
					break
		if i != 0 and j != 0:
			ans += (ls2[a] * j + sum2) * (ls2[a] * i + sum1)
	print(ans % 1000000007)


import bisect
import itertools
from random import randint

def solve(p, q, r, a, b, c, a_sum, c_sum):
	sum_ = 0
	done = {}
	for b_i in b:
		if b_i in done:
			sum_ += done[b_i]
			continue
		a_lim = bisect.bisect(a, b_i)
		c_lim = bisect.bisect(c, b_i)
		sum_b = 0
		if a_lim == 0 or c_lim == 0:
			pass
		else:
			sum_b = (a_lim * b_i + a_sum[a_lim - 1]) * (c_lim * b_i + c_sum[c_lim - 1])
		sum_ += sum_b
		done[b_i] = sum_b
	return sum_ % 1000000007

def main():
	t = int(input())
	for _ in range(t):
		(p, q, r) = [int(x) for x in input().split()]
		a = [int(x) for x in input().split()]
		a.sort()
		a_sum = list(itertools.accumulate(a))
		b = [int(x) for x in input().split()]
		b.sort()
		c = [int(x) for x in input().split()]
		c.sort()
		c_sum = list(itertools.accumulate(c))
		print(solve(p, q, r, a, b, c, a_sum, c_sum))

def test():
	t = 5
	n = 3
	for _ in range(t):
		(p, q, r) = (n, n, n)
		a = []
		for _ in range(p):
			a.append(randint(0, n))
		a.sort()
		a_sum = list(itertools.accumulate(a))
		b = []
		for _ in range(q):
			b.append(randint(0, n))
		b.sort()
		c = []
		for _ in range(r):
			c.append(randint(0, n))
		c.sort()
		c_sum = list(itertools.accumulate(c))
		print(a)
		print(b)
		print(c)
		print(solve(p, q, r, a, b, c, a_sum, c_sum))
		print('')
main()


__author__ = ['vjn4006(Vaibhav Nagda)']

def main():
	t = int(input().strip())
	for _ in range(t):
		(l, m, n) = map(int, input().strip().split(' '))
		a = sorted(list(map(int, input().strip().split(' '))))
		b = sorted(list(map(int, input().strip().split(' '))))
		c = sorted(list(map(int, input().strip().split(' '))))
		x = 0
		y = 0
		cnt_a = 0
		cnt_b = 0
		ans = 0
		a_add = 0
		c_add = 0
		for i in b:
			for j in range(x, l):
				if i >= a[j]:
					cnt_a += 1
					x += 1
					a_add += a[j]
				else:
					break
			for j in range(y, n):
				if i >= c[j]:
					cnt_b += 1
					y += 1
					c_add += c[j]
				else:
					break
			ans += (a_add + cnt_a * i) % (10 ** 9 + 7) * (c_add + cnt_b * i) % (10 ** 9 + 7) % (10 ** 9 + 7)
		print(ans % (10 ** 9 + 7))
	return
main()


from sys import stdin, stdout
t = stdin.readline()
t = int(t)
M = 1000000007
for i in range(t):
	length = [int(x) for x in stdin.readline().split()]
	a = [int(x) for x in stdin.readline().split()]
	b = [int(x) for x in stdin.readline().split()]
	c = [int(x) for x in stdin.readline().split()]
	a.sort()
	b.sort()
	c.sort()
	a.append(-1)
	c.append(-1)
	x = 0
	y = 0
	z = 0
	s = 0
	sum_x = 0
	sum_z = 0
	for y in range(0, length[1]):
		while x < length[0] and a[x] <= b[y]:
			sum_x += a[x]
			x = x + 1
		while z < length[2] and c[z] <= b[y]:
			sum_z += c[z]
			z += 1
		s = s + (sum_x % M + x % M * (b[y] % M) % M) * (sum_z % M + z % M * (b[y] % M) % M) % M
	print(s % M)


T = int(input())
ans = []
mod = 10 ** 9 + 7
for _ in range(T):
	(p, q, r) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	B = [int(i) for i in input().split()]
	C = [int(i) for i in input().split()]
	A.sort()
	B.sort()
	C.sort()
	m = 0
	n = 0
	sum1 = 0
	sum2 = 0
	count = 0
	for i in B:
		while m < p and A[m] <= i:
			sum1 += A[m]
			m += 1
		while n < r and C[n] <= i:
			sum2 += C[n]
			n += 1
		count += (sum1 + m * i) * (sum2 + n * i)
	ans.append(count % mod)
for i in ans:
	print(i)


t = int(input())
for i in range(t):
	(p, q, r) = map(int, input().split())
	arr1 = sorted(list(map(int, input().split())))
	arr2 = sorted(list(map(int, input().split())))
	arr3 = sorted(list(map(int, input().split())))
	a = b = c = d = 0
	n = 0
	mod = 10 ** 9 + 7
	for i in arr2:
		while a < p and arr1[a] <= i:
			c += arr1[a]
			a += 1
		while b < r and arr3[b] <= i:
			d += arr3[b]
			b += 1
		n += (i * a + c) * (i * b + d)
		n %= mod
	print(n)


t = int(input())
while t > 0:
	p_a = []
	q_a = []
	r_a = []
	(p, q, r) = input().split()
	(p, q, r) = (int(p), int(q), int(r))
	p_a = list(map(int, input().split()))
	q_a = list(map(int, input().split()))
	r_a = list(map(int, input().split()))
	p_a.sort()
	q_a.sort()
	r_a.sort()
	tsum = 0
	sumx = 0
	sumz = 0
	x = 0
	z = 0
	for i in range(0, q):
		while x < p and p_a[x] <= q_a[i]:
			sumx = sumx + p_a[x]
			x = x + 1
		while z < r and r_a[z] <= q_a[i]:
			sumz = sumz + r_a[z]
			z = z + 1
		val = sumx * sumz + q_a[i] * q_a[i] * x * z + (sumx * z + sumz * x) * q_a[i]
		tsum = tsum + val
	tsum = tsum % 1000000007
	print(tsum)
	t = t - 1


MODVAL = 10 ** 9 + 7
for t in range(int(input())):
	(p, q, r) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = list(map(int, input().split()))
	A.sort()
	B.sort()
	C.sort()
	ans = i = j = Xsum = Zsum = XZsum = 0
	for Y in B:
		while i < p and A[i] <= Y:
			XZsum += A[i] * Zsum
			Xsum += A[i]
			i += 1
		while j < r and C[j] <= Y:
			XZsum += C[j] * Xsum
			Zsum += C[j]
			j += 1
		ans = (ans + i * j * Y * Y + j * Xsum * Y + i * Zsum * Y + XZsum) % MODVAL
	print(ans)


t = int(input())
for temp in range(0, t):
	(p, q, r) = map(int, input().strip().split())
	mod = 1000000007
	res = 0
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	c = list(map(int, input().strip().split()))
	a.sort()
	b.sort(reverse=True)
	c.sort()
	j = p - 1
	k = r - 1
	bc = [0] * q
	ba = [0] * q
	for i in range(0, q):
		while j >= 0 and b[i] < a[j]:
			j -= 1
		while k >= 0 and b[i] < c[k]:
			k -= 1
		ba[i] = j + 1
		bc[i] = k + 1
	suma = [0] * (p + 1)
	sumc = [0] * (r + 1)
	for i in range(1, p + 1):
		suma[i] = (suma[i - 1] + a[i - 1]) % mod
	for i in range(1, r + 1):
		sumc[i] = (sumc[i - 1] + c[i - 1]) % mod
	for i in range(0, q):
		res = res + ba[i] * bc[i] % mod * b[i] % mod * b[i]
		res = res + suma[ba[i]] * b[i] % mod * bc[i]
		res = res + sumc[bc[i]] * b[i] % mod * ba[i]
		res = res + suma[ba[i]] * sumc[bc[i]]
		res %= mod
	print(res % mod)