Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are given two sequences $A$ and $B$, each with size $M$, and an integer $N$. Consider the following pseudocode:

result := 0
for i := 1 to M
for j := 1 to M
array fib[1..max(2, N)]
fib[1] := A[i]
fib[2] := B[j]
for k := 3 to N
fib[k] := fib[k-1] + fib[k-2]
result := result + fib[N]

Compute the final value of the variable result. Since it can be very large, compute its remainder modulo $10^{9}+7$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-seperated integers $M$ and $N$.
The second line contains $M$ space-seperated integers $A_{1}, A_{2}, \dots, A_{M}$.
The third line contains $M$ space-seperated integers $B_{1}, B_{2}, \dots, B_{M}$.

------  Output ------
For each test case, print the final value of result modulo $10^{9}+7$.

------  Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ M ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i}, B_{i} ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (20 points): $1 ≤ N, M ≤ 100$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
1
3 3
1 2 3
4 5 6
----- Sample Output 1 ------ 
63
----- explanation 1 ------ 
Example case 1: The innermost loop is ran for 9 pairs of initial values: $(1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)$. The corresponding values added to result are 
$5, 6, 7, 6, 7, 8, 7, 8, 9$, and their sum is 63.

Source: codechef | Difficulty: MEDIUM
Tags: Matrices

Mathematics


Solutions:
def f(h):
	if h == 1:
		return 1
	elif h == 2:
		return 1
	else:
		a = 1
		b = 1
		for i in range(h - 2):
			c = a + b
			a = b
			b = c
		return b
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	w = sum(a)
	e = sum(b)
	y = 10 ** 9 + 7
	ans = m * ((f(n - 2) % y * (w % y) % y + f(n - 1) % y * (e % y) % y) % y) % y
	if n == 1:
		print(w % y * m % y)
	elif n == 2:
		print(e % y * m % y)
	else:
		print(ans)


def multiply(a, m, mod):
	fst = a[0][0] * m[0][0] + a[0][1] * m[1][0]
	sec = a[0][0] * m[0][1] + a[0][1] * m[1][1]
	trd = a[1][0] * m[0][0] + a[1][1] * m[1][0]
	fur = a[1][0] * m[0][1] + a[1][1] * m[1][1]
	(a[0][0], a[0][1]) = (fst % mod, sec % mod)
	(a[1][0], a[1][1]) = (trd % mod, fur % mod)

def power(a, n, mod):
	if n == 0 or n == 1:
		return
	power(a, n // 2, mod)
	multiply(a, a, mod)
	if n % 2 != 0:
		m = [[1, 1], [1, 0]]
		multiply(a, m, mod)

def fib(n, mod):
	if n == 0:
		return 0
	a = [[1, 1], [1, 0]]
	power(a, n - 1, mod)
	return a
t = int(input())
mod = 10 ** 9 + 7
while t:
	t -= 1
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	suma = sum(a) * m % mod
	sumb = sum(b) * m % mod
	if n == 1:
		print(suma % mod)
	elif n == 2:
		print(sumb % mod)
	else:
		matrix = fib(n - 1, mod)
		ans = (matrix[0][0] * sumb + matrix[0][1] * suma) % mod
		print(ans)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	M = 1000000007
	A = [0, 1]
	B = [1, 0]
	for i in range(n):
		A.append(A[-1] + A[-2])
		B.append(B[-1] + B[-2])
	u = A[n - 1]
	v = B[n - 1]
	print(m * (v * sum(a) + u * sum(b)) % M)


mod = 1000000007

def multiply(mat1, mat2):
	mat3 = [[0, 0], [0, 0]]
	mat3[0][0] = mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0]
	mat3[0][1] = mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1]
	mat3[1][0] = mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0]
	mat3[1][1] = mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1]
	return mat3

def power(mat, n):
	if n == 0:
		a = [[1, 0], [0, 1]]
		return a
	if n == 1:
		return mat
	y = power(mat, int(n // 2))
	if n & 1:
		return multiply(mat, multiply(y, y))
	else:
		return multiply(y, y)
t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	l1 = list([int(x) for x in input().split()])
	l2 = list([int(x) for x in input().split()])
	d1 = dict()
	d2 = dict()
	f1 = 0
	f2 = 0
	for j in range(0, m):
		f1 += l1[j]
		f2 += l2[j]
	f1 = m * f1 % mod
	f2 = m * f2 % mod
	ans = 0
	mat = [[1, 1], [1, 0]]
	if n == 1:
		print(f1 % mod)
	elif n == 2:
		print(f2 % mod)
	elif n > 2:
		mat = power(mat, n - 2)
		ans = mat[0][0] * f2 + mat[0][1] * f1
		print(ans % mod)


for _ in range(int(input())):
	(M, N) = map(int, input().split())
	(A, B, result, a, b) = (list(map(int, input().split())), list(map(int, input().split())), 0, [0, 1], [1, 0])
	for i in range(N):
		(a.append(a[-1] + a[-2]), b.append(b[-1] + b[-2]))
	print(M * (b[N - 1] * sum(A) + a[N - 1] * sum(B)) % 1000000007)


def dbfb(A, B, m, n):
	fibo = [0, 1, 1]
	MOD = 10 ** 9 + 7
	for i in range(10 ** 5):
		fibo.append((fibo[-1] % MOD + fibo[-2] % MOD) % MOD)
	(Amod, Bmod) = (0, 0)
	for i in range(m):
		Amod = (Amod + A[i] % MOD) % MOD
		Bmod = (Bmod + B[i] % MOD) % MOD
	if n >= 3:
		return (fibo[n - 2] * m % MOD * Amod % MOD + fibo[n - 1] * m % MOD * Bmod % MOD) % MOD
	elif n == 2:
		return m * Bmod % MOD
	elif n == 1:
		return m * Amod % MOD
t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print(dbfb(A, B, m, n))


def fun():
	test = int(input())
	for t in range(test):
		(m, n) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		a = [0, 1]
		b = [1, 0]
		for i in range(n):
			a.append(a[-1] + a[-2])
			b.append(b[-1] + b[-2])
		u = a[n - 1]
		v = b[n - 1]
		print(m * (v * sum(A) + u * sum(B)) % (pow(10, 9) + 7))
fun()


def fibonacci(n, x1a, x2a):
	a = x1a
	b = x2a
	for i in range(2, n):
		c = a + b
		a = b
		b = c
	return b
T = int(input())
for i in range(T):
	(M, N) = [int(j) for j in input().split(' ')]
	A = list(map(int, input().strip().split(' ')))
	B = list(map(int, input().strip().split(' ')))
	C = A + B
	x1 = 0
	x2 = 0
	k = 0
	for i in range(0, M):
		x1 = x1 + C[i]
		x2 = x2 + C[i + M]
	if N == 1:
		k = k + x1
	elif N == 2:
		k = k + x2
	else:
		r = fibonacci(N, x1, x2)
		k = k + r
	print(k * M % 1000000007)


def fibo(a, b, n):
	for i1 in range(3, n + 1):
		c = a + b
		(a, b) = (b, c)
	return b
t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	if n > 2:
		x = fibo(1, 0, n)
		y = fibo(0, 1, n)
	elif n == 2:
		(x, y) = (0, 1)
	elif n == 1:
		(x, y) = (1, 0)
	print((m * x * sum(A) + m * y * sum(B)) % (pow(10, 9) + 7))


import math
a = int(input())
for _ in range(a):
	aa = list(map(int, input().split()))
	bb = list(map(int, input().split()))
	cc = list(map(int, input().split()))
	arr = [1, 1]
	brr = [0, 1]
	if aa[1] >= 3:
		for i in range(2, aa[1]):
			arr.append(arr[-1] + arr[-2])
			brr.append(brr[-1] + brr[-2])
		num1 = arr[-1] - brr[-1]
		num2 = brr[-1]
		result = 0
		results = sum(cc) * num2
		result = (sum(bb) * len(cc) * num1 % (10 ** 9 + 7) + results * len(cc) % (10 ** 9 + 7)) % (10 ** 9 + 7)
		print(result)
	elif aa[1] == 1:
		print(sum(bb) * aa[0] % (10 ** 9 + 7))
	else:
		print(sum(cc) * aa[0] % (10 ** 9 + 7))


t = int(input())
mod = 1000000007
while t > 0:
	t -= 1
	(m, n) = input().split()
	(m, n) = (int(m), int(n))
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	(x, y) = (sum(a) * m, sum(b) * m)
	for i in range(2, n):
		(x, y) = (y, (x + y) % mod)
	if n != 1:
		print(y)
	else:
		print(x)


def relationa(n):
	if n == 1:
		return 1
	else:
		return relationb(n - 1)

def relationb(n):
	if n == 1:
		return 0
	else:
		return relationa(n - 1) + relationb(n - 1)

def fibs(n):
	l = [0, 1]
	if n == 1 or n == 2:
		return l
	else:
		for i in range(2, n):
			temp = sum(l)
			l[0] = l[1]
			l[1] = temp
		return l
n = int(input())
for i in range(n):
	inp = list(map(int, input().split()))
	m = inp[0]
	n = inp[1]
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	suma = sum(a)
	sumb = sum(b)
	po = fibs(n)
	summ = m * suma * po[0] + m * sumb * po[1]
	print(summ % 1000000007)


def arr_sum(a):
	s = 0
	for i in a:
		s = (s + i) % (10 ** 9 + 7)
	return s
for _ in range(int(input())):
	(m, n) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	result = 0
	if n == 1:
		acoef = 1
		bcoef = 0
	elif n == 2:
		acoef = 0
		bcoef = 1
	else:
		t1 = (1, 0)
		t2 = (0, 1)
		for i in range(n - 2):
			acoef = (t1[0] + t2[0]) % (10 ** 9 + 7)
			bcoef = (t1[1] + t2[1]) % (10 ** 9 + 7)
			t1 = t2
			t2 = (acoef, bcoef)
	print((acoef * arr_sum(a) + bcoef * arr_sum(b)) % (10 ** 9 + 7) * m % (10 ** 9 + 7))


t = int(input())
for i in range(0, t):
	(m, n) = input().split()
	m = int(m)
	n = int(n)
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	result = 0
	c = sum(a) * m
	d = sum(b) * m
	if n is 1:
		print(c % 1000000007)
	elif n is 2:
		print(d % 1000000007)
	else:
		for k in range(2, n):
			result = c + d
			c = d
			d = result
		print(result % 1000000007)


MOD = 1000000007
t = int(input())
while t > 0:
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s1 = sum(a) * m
	s2 = sum(b) * m
	if n == 1:
		print(s1)
	elif n == 2:
		print(s2)
	else:
		for i in range(2, n):
			s3 = s1 + s2
			s1 = s2
			s2 = s3
		print(s3 % MOD)
	t -= 1


z = 1000000007

def moduloFibo(n):
	if n == 1 or n == 2:
		return 1
	fib = 0
	fibPrevPrev = 1
	fibPrev = 1
	for i in range(3, n + 1):
		fib = (fibPrevPrev + fibPrev) % z
		if i == n:
			return fib
		fibPrevPrev = fibPrev
		fibPrev = fib

def result(a, b, n):
	if n == 1:
		m = len(a)
		sum = 0
		for i in range(m):
			sum = (sum + a[i] % z) % z
		return m % z * sum % z
	elif n == 2:
		m = len(b)
		sum = 0
		for i in range(m):
			sum = (sum + b[i] % z) % z
		return m % z * sum % z
	else:
		m = len(a)
		sa = 0
		for i in range(m):
			sa = (sa + a[i] % z) % z
		sb = 0
		for i in range(m):
			sb = (sb + b[i] % z) % z
		p1 = sa * moduloFibo(n - 2) % z
		p2 = sb * moduloFibo(n - 1) % z
		return m % z * (p1 + p2) % z % z
t = int(input())
for i in range(t):
	(m, n) = input().split()
	m = int(m)
	n = int(n)
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	print(result(a, b, n))


def mul_a_wd_m(a, m):
	a_new = []
	for el in a:
		prod = el * m
		a_new.append(prod)
	return a_new

def sum_of_b(b):
	sum_b = sum(b)
	return sum_b
t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	modulo = 1000000007
	sum_b = 0
	sum_a = 0
	result = 0
	if n == 1:
		result = sum(a) * m
	elif n == 2:
		result = sum(b) * m
	else:
		a = mul_a_wd_m(a, m)
		sum_a = sum(a)
		sum_b = sum_of_b(b) * m
		sum_ab = sum_a + sum_b
		rng = n - 3
		for j in range(rng):
			sum_a = sum_b
			sum_b = sum_ab
			sum_ab = sum_a + sum_b
		result = sum_ab
	modulo_result = result % modulo
	print(modulo_result)


t = int(input())
while t > 0:
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mod = 1000000007
	sum1 = 0
	sum2 = 0
	for num in a:
		sum1 += num
	for num in b:
		sum2 += num
	result = []
	result.append(sum1)
	result.append(sum2)
	i = 2
	while i < n:
		x = (result[i - 1] + result[i - 2]) % mod
		result.append(x)
		i += 1
	ans = 0
	for num in range(m):
		ans = (ans + result[n - 1]) % mod
	print(ans)
	t -= 1


def main():
	fib = [0, 1]
	for i in range(100000):
		fib.append((fib[-2] + fib[-1]) % 1000000007)
	t = int(input())
	for _ in range(t):
		n = input()
		[m, n] = n.split(' ')
		m = int(m)
		n = int(n)
		a = [int(i) for i in input().split(' ')]
		b = [int(i) for i in input().split(' ')]
		sum_a = 0
		sum_b = 0
		result = 0
		for i in a:
			sum_a += i
			sum_a = sum_a % 1000000007
		for i in b:
			sum_b += i
			sum_b = sum_b % 1000000007
		if n == 1:
			result += sum_a * m % 1000000007
			result = result % 1000000007
		elif n == 2:
			result += sum_b * m % 1000000007
			result = result % 1000000007
		else:
			diff1 = (sum_a - m) * m % 1000000007
			diff2 = (sum_b - m) * m % 1000000007
			result += (diff1 * fib[n - 2] % 1000000007 + diff2 * fib[n - 1] % 1000000007) % 1000000007
			result = result % 1000000007
			result += m * m % 1000000007 * fib[n] % 1000000007
			result = result % 1000000007
		print(result % 1000000007)
main()


t = int(input())
while t > 0:
	a1 = 1
	a2 = 1
	a3 = 0
	ind = list(map(int, input().split(' ')))
	m = ind[0]
	n = ind[1]
	sum1 = 0
	sum2 = 0
	result = 0
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	for j in range(0, m):
		sum1 = sum1 + a[j]
		sum2 = sum2 + b[j]
	for k in range(n - 3):
		a3 = a1 + a2
		a1 = a2
		a2 = a3
	if n == 1:
		a1 = 1
		a2 = 0
		result = m * sum1 % 1000000007
	elif n == 2:
		a1 = 0
		a2 = 1
		result = m * sum2 % 1000000007
	else:
		result = m * (a1 * sum1 + a2 * sum2) % 1000000007
	print(result)
	t = t - 1


def getNthFib(i, j, n):
	if n == 1 or n == 2:
		return n
	k = i + j
	count = 3
	while count < n:
		i = j
		j = k
		k = i + j
		count += 1
	return k

def getResult(a, b, n):
	result = 0
	l = len(a)
	A3 = sum(a) + l * b[0]
	A4 = A3 + l * b[0]
	if n == 1:
		return sum(a) * l
	elif n == 2:
		return sum(b) * l
	if n >= 4:
		An = getNthFib(A3, A4, n - 2)
	elif n == 3:
		An = A3
	else:
		An = A4
	p = 0
	for i in range(1, l):
		p += (l - i) * (b[i] - b[i - 1])
	p = p * getNthFib(1, 2, n - 2) + An
	result = p * l
	return result
t = int(input())
for i in range(t):
	(M, N) = map(int, input().split())
	a_arr = [int(k) for k in input().split()]
	b_arr = [int(k) for k in input().split()]
	print(getResult(a_arr, b_arr, N) % (10 ** 9 + 7))


T = int(input())
for t in range(T):
	mn = list(map(int, input().split()))
	m = mn[0]
	n = mn[1]
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = sum(a) * m
	b = sum(b) * m
	fib = [0] * max(2, n)
	fib[0] = a
	fib[1] = b
	for j in range(2, n):
		fib[j] = fib[j - 1] + fib[j - 2]
	print(fib[n - 1] % 1000000007)


t = int(input())
for i in range(t):
	d = 10 ** 9 + 7
	(m, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	s1 = sum(a) * m
	s2 = sum(b) * m
	if k == 1:
		print(s1 % d)
	if k == 2:
		print(s2 % d)
	if k > 2:
		for i in range(3, k + 1):
			c = (s1 + s2) % d
			s1 = s2
			s2 = c
		print(s2 % d)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(result, suma, sumb) = (0, 0, 0)
	fib = [0] * max(2, n)
	for i in range(m):
		suma = suma + m * a[i]
		sumb = sumb + m * b[i]
		fib[0] = suma
		fib[1] = sumb
	for k in range(2, n):
		fib[k] = fib[k - 1] + fib[k - 2]
	result = fib[n - 1]
	print(result % (10 ** 9 + 7))


def f(s1, s2, t):
	d = [0] * t + [0]
	(d[0], d[1]) = (s1, s2)
	for i in range(2, t):
		d[i] = d[i - 1] + d[i - 2]
	return d[t - 1]
t = int(input())
while t > 0:
	(m, n) = input().split(' ')
	a = [int(x) for x in input().split(' ')]
	b = [int(x) for x in input().split(' ')]
	sum1 = sum(a) * int(m)
	sum2 = sum(b) * int(m)
	res = f(sum1, sum2, int(n))
	M = 1000000007
	print(res % M)
	t -= 1


def fibs(M, N, A, B):
	n = 0
	result = 0
	fib = [0, 1, 2]
	n = max(2, N)
	while len(fib) < n + 1:
		fib.append(0)
	fib[1] = A
	fib[2] = B
	for k in range(3, n + 1):
		fib[k] = fib[k - 1] + fib[k - 2]
	result = fib[n]
	ans1 = result % (10 ** 9 + 7)
	print(ans1)
T = int(input())
while T > 0:
	sumA = 0
	sumB = 0
	mandn = input().split()
	N = int(mandn[1])
	M = int(mandn[0])
	A = input().split()
	B = input().split()
	for j in range(0, M):
		sumA = sumA + M * int(A[j])
		sumB = sumB + M * int(B[j])
	fibs(M, N, sumA, sumB)
	T = T - 1


test = int(input())
for i in range(test):
	(M, N) = map(int, input().strip().split())
	A = list(map(int, input().strip().split()))
	B = list(map(int, input().strip().split()))
	FibSeries = []
	result = 0
	sumB = 0
	sumA = 0
	fib = []
	FibSeries.append(0)
	FibSeries.append(1)
	fib.append(A[0])
	fib.append(B[0])
	for z in range(2, N, 1):
		FibSeries.append(FibSeries[z - 1] + FibSeries[z - 2])
		fib.append(fib[z - 1] + fib[z - 2])
	for j in range(M):
		sumB = sumB + (B[j] - B[0])
		sumA = sumA + (A[j] - A[0])
	z = sumB * FibSeries[-1]
	y = sumA * FibSeries[-2] + M * fib[-1]
	result = M * (y + z)
	print(result % (10 ** 9 + 7))
	test = test + 1


T = int(input())
for t in range(T):
	lis = list(map(int, input().split()))
	m = lis[0]
	n = lis[1]
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = 1000000007
	fiba = [0] * (n + 2)
	fiba[1] = 1
	fiba[2] = 0
	for i in range(3, n + 2):
		fiba[i] = fiba[i - 1] + fiba[i - 2]
	print((fiba[n] * sum(a) + fiba[n + 1] * sum(b)) * m % p)


mod = 10 ** 9 + 7

def fun(a, b, n, m):
	(res, ax, bx) = (0, 0, 0)
	for i in range(m):
		ax += a[i]
	for i in range(m):
		bx += b[i]
	(ax, bx) = (ax * m % mod, bx * m % mod)
	fib = [ax, bx]
	for i in range(2, max(2, n)):
		fib.append(fib[i - 1] % mod + fib[i - 2] % mod)
	return fib[max(2, n) - 1] % mod
for i in range(int(input())):
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(fun(a, b, n, m))


t = int(input())
while t > 0:
	(m, n) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	B = [int(i) for i in input().split()]
	div = 1000000007
	fib = [(1, 0), (0, 1)]
	for i in range(2, 100001):
		fib.append(((fib[i - 1][0] + fib[i - 2][0]) % div, (fib[i - 1][1] + fib[i - 2][1]) % div))
	res = 0
	for i in range(m):
		res += (A[i] * fib[n - 1][0] + B[i] * fib[n - 1][1]) % div
	res = res * m
	res = res % div
	print(res)
	t -= 1


t = int(input())
for i in range(t):
	s1 = list(map(int, input().split()))
	m = int(s1[0])
	n = int(s1[1])
	s2 = list(map(int, input().split()))
	s3 = list(map(int, input().split()))
	sum1 = sum(s2)
	sum2 = sum(s3)
	fib = [0] * max(2, n)
	fib[0] = m * sum1
	fib[1] = m * sum2
	for j in range(2, n):
		fib[j] = fib[j - 1] + fib[j - 2]
	print(fib[n - 1] % 1000000007)


mod = 1000000007
fibs = [(1, 0), (0, 1)]
for i in range(2, 100001):
	fibs.append(((fibs[i - 1][0] + fibs[i - 2][0]) % mod, (fibs[i - 1][1] + fibs[i - 2][1]) % mod))
t = int(input())
while t > 0:
	(m, n) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	res = 0
	for i in range(m):
		res = res + (a[i] * fibs[n - 1][0] + b[i] * fibs[n - 1][1]) % mod
	res = res * m
	print(res % mod)
	t = t - 1


t = int(input())
for _ in range(t):
	(m, n) = [int(x) for x in input().split(' ')]
	result = 0
	a = [int(x) for x in input().split(' ')]
	b = [int(x) for x in input().split(' ')]
	a1 = 1
	a2 = 1
	a3 = 0
	a_sum = 0
	b_sum = 0
	for i in range(m):
		a_sum = (a_sum + a[i]) % 1000000007
		b_sum = b_sum + b[i] % 1000000007
	for i in range(n - 3):
		a3 = a1 + a2
		a1 = a2
		a2 = a3
	if n == 2:
		a1 = 0
		a2 = 1
		print(m * b_sum % 1000000007)
	elif n == 1:
		a1 = 1
		a2 = 0
		print(m * a_sum % 1000000007)
	else:
		result = m * (a1 * a_sum + a2 * b_sum)
		print(result % 1000000007)


modulo = pow(10, 9) + 7
T = int(input())
for j in range(T):
	s = input()
	s = s.split()
	M = int(s[0])
	N = int(s[1])
	a = input()
	a = a.split()
	b = input()
	b = b.split()
	for i in range(M):
		a[i] = int(a[i])
		b[i] = int(b[i])
	sum_a = 0
	sum_b = 0
	for i in range(M):
		sum_a += a[i]
		sum_b += b[i]
	result = 0
	sum_a *= M
	sum_b *= M
	if N == 1:
		result = sum_a % modulo
	elif N == 2:
		result = sum_b % modulo
	else:
		var = 0
		x = sum_a
		y = sum_b
		k = 2
		while N > k:
			var = (x + y) % modulo
			x = y
			y = var
			k += 1
		result = var % modulo
	print(result)


t = int(input())
while t > 0:
	t = t - 1
	(m, n) = input().split()
	m = int(m)
	n = int(n)
	d = 1000000007
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	result = 0
	sum1 = sum2 = 0
	for i in range(m):
		sum1 = (sum1 + a[i]) % d
		sum2 = (sum2 + b[i]) % d
	if n == 1:
		result = sum1 * m % d
		print(result)
	elif n == 2:
		result = sum2 * m % d
		print(result)
	else:
		x = 0
		y = 1
		ans = 1
		k = n - 2
		while k > 0:
			ans = (x + y) % d
			x = y
			y = ans
			k = k - 1
		result = (sum1 * x % d * m % d + sum2 * ans % d * m % d) % d
		print(result)


for case in range(int(input())):
	(m, n) = (int(i) for i in input().split())
	p = sum([int(i) for i in input().split()]) * m
	q = sum([int(i) for i in input().split()]) * m
	for i in range(n - 1):
		(p, q) = (q, p + q)
	print(p % (10 ** 9 + 7))


t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	result = 0
	t = 0
	if n > 2:
		size = n
	else:
		size = 2
	fib1 = 0
	fib2 = 0
	for i in range(len(a)):
		fib1 = fib1 + a[i] * m
		fib2 = fib2 + b[i] * m
	for k in range(2, size):
		s = fib2
		fib2 = fib1 + fib2
		fib1 = s
	result = result + fib2
	print(result % (10 ** 9 + 7))


for case in range(int(input())):
	(m, n) = (int(i) for i in input().split())
	a = sum([int(i) for i in input().split()]) * m
	b = sum([int(i) for i in input().split()]) * m
	for i in range(n - 1):
		(a, b) = (b, a + b)
	print(a % (10 ** 9 + 7))


import math
import copy
t = int(input())
while t > 0:
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	modulo = 1000000007
	sum_a = 0
	sum_b = 0
	for i in a:
		sum_a += i % modulo
		sum_a = sum_a % modulo
	for i in b:
		sum_b += i % modulo
		sum_b = sum_b % modulo
	sum_a = sum_a * m % modulo
	sum_b = sum_b * m % modulo
	l = list()
	l.append(sum_a)
	l.append(sum_b)
	for i in range(2, n):
		l.append((l[i - 1] + l[i - 2]) % modulo)
	print(l[-1])
	t -= 1


mod = 1000000007
xCoeff = [0] * 100000
yCoeff = [0] * 100000
xCoeff[0] = 1
yCoeff[0] = 1
for i in range(1, 100000):
	yCoeff[i] = (xCoeff[i - 1] + yCoeff[i - 1]) % mod
	xCoeff[i] = yCoeff[i - 1] % mod
tCases = int(input())
while tCases > 0:
	(M, N) = list(map(lambda x: int(x), input().split()))
	aryA = list(map(lambda x: int(x), input().split()))
	aryB = list(map(lambda x: int(x), input().split()))
	sumA = 0
	sumB = 0
	for i in range(M):
		sumA = (sumA + aryA[i]) % mod
		sumB = (sumB + aryB[i]) % mod
	if N >= 3:
		result = (xCoeff[N - 3] * (sumA % mod) % mod + yCoeff[N - 3] * (sumB % mod) % mod) % mod * M % mod
	elif N == 1:
		result = M * sumA % mod
	elif N == 2:
		result = M * sumB % mod
	print(result)
	tCases = tCases - 1


import sys
sys.setrecursionlimit(10 ** 9)
global p
p = 10 ** 9 + 7

def fib(l, l1, n):
	if n == 1:
		return l
	if n == 2:
		return l1
	n -= 2
	while n > 0:
		l2 = [(l[0] + l1[0]) % p, (l[1] + l1[1]) % p]
		(l, l1) = (l1, l2)
		n -= 1
	return l2
test = int(input())
while test > 0:
	test -= 1
	(m, n) = map(int, input().split())
	a = sum(list(map(int, input().split())))
	b = sum(list(map(int, input().split())))
	c = fib([1, 0], [0, 1], n)
	(c0, c1) = (c[0], c[1])
	c = 0
	c = c0 * a % p
	c += c1 * b % p
	c = c * m
	c %= p
	print(c)


def method1(A, B):
	result = 0
	for i in range(M):
		for j in range(M):
			fib = []
			fib.append(A[i])
			fib.append(B[j])
			for k in range(2, N):
				fib.append(fib[k - 1] + fib[k - 2])
			result += fib[N - 1]
	return result % MOD

def method2(A, B):

	class AB(object):

		def __init__(self, A, B):
			self.A = A
			self.B = B
	if N == 1:
		fib_n = AB(1, 0)
	elif N == 2:
		fib_n = AB(0, 1)
	else:
		fib_x_1 = AB(1, 0)
		fib_x_2 = AB(0, 1)
		for k in range(N - 2):
			newA = fib_x_1.A + fib_x_2.A
			newB = fib_x_1.B + fib_x_2.B
			fib_x_3 = AB(newA, newB)
			(fib_x_1, fib_x_2) = (fib_x_2, fib_x_3)
		fib_n = fib_x_3
	result = 0
	result += fib_n.A * sum(A) * M + fib_n.B * sum(B) * M
	return result % MOD
T = int(input())
MOD = 10 ** 9 + 7
for _ in range(T):
	(M, N) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	print(method2(A, B))


def fib(a, b, n):
	for _ in range(n):
		(a, b) = (b, a + b)
	return a
ModAmt = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	(M, N) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	(A, B) = (M * sum(A), M * sum(B))
	result = fib(A, B, N - 1)
	result %= ModAmt
	print(result)


t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	i1 = list(map(int, input().split()))
	i2 = list(map(int, input().split()))
	googly = 0
	mod = 1000000007
	googly1 = 0
	for j in range(m):
		googly = (googly + i1[j]) % mod
		googly1 = (googly1 + i2[j]) % mod
	if n == 1:
		print(googly * m % mod)
		continue
	if n == 2:
		print(googly1 * m % mod)
		continue
	a = []
	a.append(1)
	a.append(1)
	for j in range(2, n + 2):
		a.append((a[j - 1] + a[j - 2]) % mod)
	value = googly * a[n - 3] % mod + googly1 * a[n - 2] % mod
	value = value * m % mod
	print(value)


t = int(input())
mod = 1000000007
for _ in range(t):
	cnt = 0
	(m, n) = list(map(int, input().split()))
	sz = max(2, n)
	result = 0
	val = 0
	init = 0
	xChange = 0
	diff = 0
	u = 0
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	fib1 = a[0]
	fib2 = b[0]
	cn = 0
	for k in range(2, n):
		cn = (fib1 % mod + fib2 % mod) % mod
		fib1 = fib2 % mod
		fib2 = cn % mod
	if n >= 3:
		x = 1
		y = 2
		if n == 3:
			diff = 1
		elif n == 4:
			diff = 2
		else:
			while cnt + 4 < n:
				diff = (x + y) % mod
				x = y % mod
				y = diff % mod
				cnt = cnt + 1
	if n == 1:
		init = a[0]
	elif n == 2:
		init = b[0]
	elif n >= 3:
		init = cn
	if n >= 3:
		for j in range(m):
			val = diff * (b[j] - b[0]) % mod
			cool = (init + val) % mod
			result = (result + cool) % mod
		u = result
		for i in range(1, m):
			if n > 3:
				xChange = x * (a[i] - a[0]) % mod % mod
			elif n == 3:
				xChange = (a[i] - a[0]) % mod
			xChange = xChange * m % mod
			xChange = (u + xChange) % mod
			result = (result + xChange) % mod
	elif n == 2:
		for i in range(m):
			result = (result + b[i]) % mod
		result = result * m % mod
	else:
		for i in range(m):
			result = (result + a[i]) % mod
		result = result * m % mod
	result = result % mod
	print(result)


def fib(a, b, n1):
	l = [a, b]
	for i in range(2, n1):
		l.append(l[i - 1] + l[i - 2])
	return l[n1 - 1]
a1 = int(input())
for _ in range(a1):
	(m, n) = [int(j) for j in input().split()]
	l1 = [int(j) for j in input().split()]
	l2 = [int(j) for j in input().split()]
	c1 = 0
	d1 = sum(l1)
	d2 = sum(l2)
	print(fib(d1, d2, n) * m % (10 ** 9 + 7))


t = int(input())
for q in range(t):
	(m, n) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	f = [0] * max(2, n)
	f[0] = sum(a) * m
	f[1] = sum(b) * m
	for w in range(2, n):
		f[w] = f[w - 1] + f[w - 2]
	print(f[n - 1] % (10 ** 9 + 7))


def fibo(numb):
	fib = [0, 1]
	for i in range(2, numb + 1):
		fib.append(fib[i - 1] + fib[i - 2])
	return fib[numb]
for t in range(int(input())):
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(res, modafoka) = (0, 1000000007)
	if n == 1:
		(ma, mb) = (1, 0)
	elif n == 2:
		(ma, mb) = (0, 1)
	else:
		(ma, mb) = (fibo(n - 2), fibo(n - 1))
	result = (ma % modafoka * (m % modafoka) * (sum(a) % modafoka) % modafoka + m % modafoka * (mb % modafoka) * sum(b)) % modafoka
	print(result)


def fib(n):
	a = 0
	b = 1
	c = 0
	for i in range(0, n - 2):
		c = a + b
		a = b
		b = c
	return (a, c)
T = int(input())
for i in range(T):
	result = 0
	(M, N) = input().split()
	M = int(M)
	N = int(N)
	if N == 1:
		(a, b) = (0, 1)
	elif N == 2:
		(a, b) = (0, 1)
	else:
		(a, b) = fib(N)
	A = input().split()
	B = input().split()
	for j in range(len(A)):
		A[j] = int(A[j])
	for j in range(len(B)):
		B[j] = int(B[j])
	sumA = 0
	sumB = 0
	for i in A:
		sumA += i
	for i in B:
		sumB += i
	result += sumA * a
	result += sumB * b
	result *= M
	print(result % 1000000007)


MOD = 1000000007
fib = [0, 0, 1]
for i in range(3, 100005):
	fib.append((fib[i - 1] + fib[i - 2]) % MOD)
T = int(input())
for _ in range(T):
	(M, N) = input().split()
	(M, N) = (int(M), int(N))
	sum_a = sum_b = 0
	A = [int(x) for x in input().split()]
	sum_a = sum(A) % MOD
	B = [int(x) for x in input().split()]
	sum_b = sum(B) % MOD
	first = sum_a * M % MOD
	second = sum_b * M % MOD
	if N is 1:
		print(first)
	elif N is 2:
		print(second)
	else:
		print((first * fib[N - 1] % MOD + second * fib[N] % MOD) % MOD)


t = int(input())
for i in range(t):
	s = input()
	s = s.split()
	m = int(s[0])
	n = int(s[1])
	a = input()
	a = a.split()
	for q in range(m):
		a[q] = int(a[q])
	b = input()
	b = b.split()
	for q in range(m):
		b[q] = int(b[q])
	x = []
	y = []
	arr = []
	x.append(1)
	x.append(0)
	y.append(0)
	y.append(1)
	arr.append(a[0])
	arr.append(b[0])
	result = 0
	for j in range(2, n):
		arr.append((arr[j - 1] + arr[j - 2]) % 1000000007)
		x.append((x[j - 1] + x[j - 2]) % 1000000007)
		y.append((y[j - 1] + y[j - 2]) % 1000000007)
	result += arr[n - 1] * m * m % 1000000007
	for j in range(m):
		result += ((a[j] - a[0]) * x[n - 1] + (b[j] - b[0]) * y[n - 1]) * m
	result = result % 1000000007
	print(result)


M = 1000000007
fib_count = [(1, 0), (0, 1)]
for i in range(2, 100001):
	fib_count.append(((fib_count[i - 1][0] + fib_count[i - 2][0]) % M, (fib_count[i - 1][1] + fib_count[i - 2][1]) % M))
t = int(input())
while t > 0:
	(m, n) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	result = 0
	for i in range(m):
		result += (a[i] * fib_count[n - 1][0] + b[i] * fib_count[n - 1][1]) % M
	result *= m
	print(result % M)
	t -= 1


t = int(input())
for i in range(t):
	fib = []
	c = 1000000007
	(total, sum) = (0, 0)
	mn = input().split()
	a = input().split()
	b = input().split()
	for j in range(int(mn[0])):
		a[j] = int(a[j])
		sum = (sum + int(b[j])) % c
	for j in range(int(mn[1])):
		if j == 1 or j == 0:
			fib.append(j)
		else:
			fib.append((fib[j - 1] + fib[j - 2]) % c)
	for j in range(int(mn[0])):
		if int(mn[1]) == 1:
			total = (total + a[j]) % c
		else:
			total = (total + int(mn[0]) * fib[int(mn[1]) - 2] % c * a[j] % c + fib[int(mn[1]) - 1] * sum % c) % c
	print(total)


import operator
mod = 1000000007
t = int(input())
for _ in range(t):
	lol = [int(i) for i in input().split()]
	m = int(lol[0])
	n = int(lol[1])
	asum = 0
	bsum = 0
	for i in input().split():
		asum += int(i)
	for i in input().split():
		bsum += int(i)
	fib = []
	fib.append((1, 0))
	fib.append((0, 1))
	for i in range(2, n + 1):
		fib.append(tuple(map(operator.add, fib[i - 1], fib[i - 2])))
	ans = (m * asum * fib[n - 1][0] % mod + m * bsum * fib[n - 1][1] % mod) % mod
	print(ans)


t = int(input())
a = [0, 1, 0]
b = [0, 0, 1]
for i in range(3, 100005):
	a.append(a[i - 1] + a[i - 2])
	b.append(b[i - 1] + b[i - 2])
for _ in range(t):
	(m, n) = map(int, input().split())
	m = int(m)
	n = int(n)
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print((sum(B) * b[n] * m + sum(A) * a[n] * m) % 1000000007)


mod = 10 ** 9 + 7
fib = [0] * 100000
fib[1] = 1
for k in range(2, 100000):
	fib[k] = (fib[k - 1] + fib[k - 2]) % mod
T = int(input())
for t in range(T):
	(m, n) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sum_a = sum(a) % mod
	sum_b = sum(b) % mod
	if n == 1:
		res = sum_a
	else:
		res = (a[0] * fib[n - 2] * m + sum_b * fib[n - 1]) % mod
	res = res * m % mod
	multiplier = n - 2
	if multiplier > 0:
		if multiplier <= 2:
			multiplier = 1
		else:
			multiplier = fib[multiplier] % mod
		diff = (sum_a - a[0] * m) % mod
		res = (res + multiplier * diff * m) % mod
	print(res % mod)


for t in range(int(input())):
	(m, n) = [int(m) for m in input().split()]
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	mod = int(1000000000.0 + 7)
	if n == 1:
		print(sum(arr1) * m % mod)
	elif n == 2:
		print(sum(arr2) * m % mod)
	else:
		(f1, f2) = (0, 1)
		for i in range(n - 2):
			(f1, f2) = (f2, f1 + f2)
		print(m * (sum(arr1) * f1 + sum(arr2) * f2) % mod)


x = int(input())
for i in range(x):
	d = 0
	f = 0
	(M, N) = map(int, input().split())
	fibonacci = [0, 1]
	for i in range(2, max(2, N)):
		fibonacci.append(fibonacci[i - 1] + fibonacci[i - 2])
	array = [int(item) for item in input().split()]
	d = sum(array)
	z = int(d) * int(M)
	t = int(z) * int(fibonacci[max(2, N) - 2])
	arr = [int(item) for item in input().split()]
	f = sum(arr)
	s = int(f) * int(M)
	q = int(s) * int(fibonacci[max(2, N) - 1])
	k = int(t) + int(q)
	print(int(k) % (1000000000 + 7))


def fibser(n1, n2, con):
	a = [0] * con
	a[0] = n1
	a[1] = n2
	for i in range(2, con):
		a[i] = a[i - 1] + a[i - 2]
	return a[-1]
tc = int(input())
while tc != 0:
	sm = 0
	n = input().split()
	a = input().split()
	b = input().split()
	n = list(map(int, n))
	a = list(map(int, a))
	b = list(map(int, b))
	sma = sum(a)
	smb = sum(b)
	if n[1] <= 2:
		print(sum(b) * len(b))
		tc -= 1
		continue
	res = fibser(sma, smb, n[1])
	result = res * len(b) % 1000000007
	print(result)
	tc -= 1


T = int(input())
for i in range(T):
	a = input()
	Q = list(map(int, a.split()))
	M = Q[0]
	N = Q[1]
	a1 = input()
	A = list(map(int, a1.split()))
	a2 = input()
	B = list(map(int, a2.split()))
	sum1 = 0
	sum2 = 0
	for i in range(M):
		sum1 = sum1 + A[i] * M
		sum2 = sum2 + B[i] * M
	if N == 1:
		print(sum1 % 1000000007)
	elif N == 2:
		print(sum2 % 1000000007)
	elif N > 2:
		while N > 2:
			temp = sum1
			sum1 = sum2
			sum2 = temp + sum2
			N = N - 1
		print(sum2 % 1000000007)


def fib(n):
	(a, b) = (0, 1)
	for i in range(0, n):
		(a, b) = (b, a + b)
	return a

def cal(suma, sumb, n, m):
	x = 1000000007
	val = m * (suma * fib(n - 2) + sumb * fib(n - 1)) % x
	return val
t = int(input())
for i in range(t):
	v = list(map(int, input().split(' ')))
	suma = 0
	sumb = 0
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	for j in range(v[0]):
		suma += a[j]
	for j in range(v[0]):
		sumb += b[j]
	if v[1] <= 2:
		if v[1] == 1:
			print(suma * v[0])
		else:
			print(sumb * v[1])
	else:
		print(cal(suma, sumb, v[1], v[0]))


MAX = 100000
f = [0] * MAX

def fibo(n):
	if n == 0:
		return 0
	if n == 1 or n == 2:
		f[n] = 1
		return f[n]
	if f[n]:
		return f[n]
	if n & 1:
		k = (n + 1) // 2
	else:
		k = n // 2
	if n & 1:
		f[n] = fibo(k) * fibo(k) + fibo(k - 1) * fibo(k - 1)
	else:
		f[n] = (2 * fibo(k - 1) + fibo(k)) * fibo(k)
	return f[n]
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	result = 0
	(sumA, sumB) = (sum(A), sum(B))
	if n == 1:
		result = sumA * m
	else:
		fib = [0] * n
		if n >= 3:
			fib[n - 1] = (fibo(n - 2) * sumA + fibo(n - 1) * sumB) * m
		if n == 2:
			fib[n - 1] = sumB * m
		result += fib[n - 1]
	print(result % 1000000007)


import math
t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mo = 1000000007
	sa = 0
	sb = 0
	for i in range(m):
		sa = (sa + a[i]) % mo
		sb = (sb + b[i]) % mo
	thr = sa * m % mo
	fou = sb * m % mo
	res = 0
	fib = [0] * max(2, n)
	fib[0] = thr
	fib[1] = fou
	for k in range(2, n):
		fib[k] = (fib[k - 1] + fib[k - 2]) % mo
	res = (res + fib[n - 1]) % mo
	print(res)


q = 10 ** 9 + 7

def fib(a, b, n):
	c = 0
	if n == 0:
		return 1
	if n == 1:
		return a
	elif n == 2:
		return b
	else:
		for i in range(3, n + 1):
			c = a + b
			a = b
			b = c
		return c
t = int(input())
for i in range(0, t):
	y = []
	z = []
	result = 0
	(m, n) = map(int, input().split())
	y = list(map(int, input().split()))
	z = list(map(int, input().split()))
	s = 0
	t = 0
	for j in range(0, m):
		s = s + y[j]
		t = t + z[j]
	result = m * (fib(0, 1, n) * t + fib(0, 1, n - 1) * s)
	print(result % q)


val = int(input())
for i in range(val):
	N1 = input().split(' ')
	N = int(N1[0])
	M = int(N1[1])
	l1 = []
	l2 = []
	l1 = input().split(' ')
	l2 = input().split(' ')
	sum3 = 0
	sum1 = 0
	sum2 = 0
	sum4 = 0
	for u in range(N):
		sum1 = N * int(l1[u]) + sum1
		sum2 = N * int(l2[u]) + sum2
		sum3 = N * (int(l1[u]) + int(l2[u])) + sum3
		sum4 = N * (int(l1[u]) + 2 * int(l2[u])) + sum4
	B = 4
	j = 1000000007
	if M == 1:
		print(sum1 % j)
	elif M == 2:
		print(sum2 % j)
	elif M == 3:
		print(sum3 % j)
	elif M == 4:
		print(sum4 % j)
	else:
		while M != B:
			B = B + 1
			qw = sum4
			sum4 = sum4 + sum3
			sum3 = qw
		print(sum4 % j)


F = [0] * 100001
F[0] = 1
F[1] = 0
for i in range(2, 100001):
	F[i] = (F[i - 1] + F[i - 2]) % 1000000007
t = int(input().strip())
for i in range(t):
	(m, n) = [int(x) for x in input().strip().split(' ')]
	a = [int(x) for x in input().strip().split(' ')]
	b = [int(x) for x in input().strip().split(' ')]
	r = 0
	for i in range(m):
		r += a[i] * F[n - 1] + b[i] * F[n]
	print(r * m % 1000000007)


t = int(input())
for it in range(t):
	(m, n) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	a = m * sum(l1)
	b = m * sum(l2)
	if n == 1:
		c = a
	elif n == 2:
		c = b
	for i in range(n - 2):
		c = a + b
		a = b
		b = c
	print(c % (10 ** 9 + 7))


mod = 1000000007
fib_map = {}
fib_map[-1] = 1
fib_map[0] = 0
fib_map[1] = 1
for n in range(2, 100001):
	fib_map[n] = (fib_map[n - 1] + fib_map[n - 2]) % mod
T = int(input())
for i in range(T):
	(M, N) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	a_times = sum(A) * M % mod
	b_times = sum(B) * M % mod
	print((a_times * fib_map[N - 2] % mod + b_times * fib_map[N - 1] % mod) % mod)


t = int(input())
r = 10 ** 9 + 7

def mul(c, d):
	return [(c[0] * d[0] + c[1] * d[2]) % r, (c[0] * d[1] + c[1] * d[3]) % r, (c[2] * d[0] + c[3] * d[2]) % r, (c[2] * d[1] + c[3] * d[3]) % r]

def prod(m, n):
	if n == 0:
		return [1, 1, 1, 1]
	if n == 1:
		return m
	p = prod(m, n // 2)
	p = mul(p, p)
	if n % 2 != 0:
		p = mul(p, m)
	return p

def func1():
	return [int(x) for x in input().split()]

def func2():
	(m, n) = func1()
	a = func1()
	b = func1()
	sa = sum(a) % r
	sb = sum(b) % r
	mat = [1, 1, 1, 0]
	if n == 1:
		return m * sa
	if n == 2:
		return m * sb
	if n > 2:
		mat = prod(mat, n - 2)
	p = mat[1] * (sa + sb) % r
	p += mat[3] * sb % r
	return m * p % r
a = []
for _ in range(t):
	a.append(func2())
for aa in a:
	print(aa)


MOD = int(1000000000.0) + 7

def fib(n):
	cur = 1
	old = 0
	i = 1
	while i < n:
		(cur, old, i) = (cur + old, cur, i + 1)
	return cur % MOD
T = int(input())
for test_case in range(T):
	(M, N) = map(int, input().split())
	A = input().split()
	B = input().split()
	(asu, bsu) = (0, 0)
	for i in range(M):
		asu += int(A[i])
		bsu += int(B[i])
		if asu >= MOD:
			asu %= MOD
		if bsu >= MOD:
			bsu %= MOD
	if N == 1:
		print(M * asu % MOD)
	elif N == 2:
		print(M * bsu % MOD)
	else:
		print(M * ((fib(N - 2) * asu % MOD + fib(N - 1) * bsu % MOD) % MOD) % MOD)


a = int(input())
for i in range(1, a + 1):
	b = [int(x) for x in input().split()]
	d = [int(z) for z in input().split()]
	e = [int(y) for y in input().split()]
	r = []
	r.append(sum(d) * b[0])
	r.append(sum(e) * b[0])
	for j in range(2, b[1]):
		r.append((r[j - 1] + r[j - 2]) % 1000000007)
	if b[1] == 1:
		print(r[0] % 1000000007)
	elif b[1] == 2:
		print(r[1] % 1000000007)
	else:
		print(r[b[1] - 1])


mod = 7 + 10 ** 9
test = int(input())
for test_case in range(test):
	(s_arr, s_fib) = map(int, input().split(' '))
	arr1 = list(map(int, input().split(' ')))
	arr2 = list(map(int, input().split(' ')))
	f1 = sum(arr1) * s_arr % mod
	f2 = sum(arr2) * s_arr % mod
	f_sum = 0
	if s_fib >= 1:
		f_sum = f1
	if s_fib >= 2:
		f_sum = f2
	if s_fib >= 3:
		f_sum = (f1 + f2) % mod
		f1 = f2
		f2 = f_sum
		for i in range(s_fib - 3):
			f_sum = (f1 + f2) % mod
			f1 = f2
			f2 = f_sum
	print(f_sum % mod)


from operator import add
mod = 7 + 10 ** 9
t = int(input())
for _ in range(t):
	r = 0
	(m, n) = map(int, input().split(' '))
	m1 = list(map(int, input().split(' ')))
	m2 = list(map(int, input().split(' ')))
	a = sum(m1) * m % mod
	b = sum(m2) * m % mod
	s = 0
	if n >= 1:
		s = a
	if n >= 2:
		s = b
	if n >= 3:
		s = (a + b) % mod
		a = b
		b = s
		for i in range(n - 3):
			s = (a + b) % mod
			a = b
			b = s
	print(s % mod)


mod = 1000000007
F = {}
F[-1] = 1
F[0] = 0
F[1] = 1

def fib(n):
	if n in F:
		return F[n]
	if n & 1:
		k = (n + 1) // 2
	else:
		k = n // 2
	if n & 1:
		F[n] = (fib(k) * fib(k) % mod + fib(k - 1) * fib(k - 1) % mod) % mod
	else:
		F[n] = (2 * fib(k - 1) + fib(k)) % mod * fib(k) % mod
	return F[n]
T = int(input())
for _ in range(T):
	(M, N) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	X = M * sum(A) % mod
	Y = M * sum(B) % mod
	print((X * fib(N - 2) % mod + Y * fib(N - 1) % mod) % mod)


test = int(input())
for i in range(test):
	helper = input()
	side = []
	side = helper.split(' ')
	M = int(side[0])
	N = int(side[1])
	A = []
	B = []
	A_sum = 0
	B_sum = 0
	val1 = input()
	A = val1.split(' ')
	for j in range(M):
		A_sum = A_sum + int(A[j])
	val2 = input()
	B = val2.split(' ')
	for j in range(M):
		B_sum = B_sum + int(B[j])
	A_sum = A_sum * M
	B_sum = B_sum * M
	arr = []
	for k in range(0, max(2, N)):
		arr.append(0)
	arr[0] = A_sum
	arr[1] = B_sum
	fval = 0
	for j in range(2, N):
		arr[j] = arr[j - 1] + arr[j - 2]
	fval = arr[N - 1] % (10 ** 9 + 7)
	print(fval)


t = int(input())
mc = 10 ** 9 + 7
fib = [0, 1] + [0 for i in range(10 ** 5)]
for i in range(2, len(fib)):
	fib[i] = (fib[i - 1] + fib[i - 2]) % mc
for i in range(t):
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	res = 0
	if n == 1:
		res = m * sum(a)
	elif n == 2:
		res = m * sum(b)
	else:
		res = m * (fib[n - 2] * sum(a) + fib[n - 1] * sum(b))
	print(res % mc)