Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef and Chefu are at a magical candy store playing a game with the following rules:
There are two candy counters; each of them stores an infinite number of candies. At any time, only one of the counters is open and the other is closed.
Exactly one player is present at each of the counters. Initially, Chef is at the open counter and Chefu is at the closed counter.
There is a sequence of $N$ distinct integers $A_{1}, A_{2}, \ldots, A_{N}$. The game consists of $R$ turns; in the $i$-th turn, the open counter offers only $C = A_{ (i-1) \% N + 1}$ candies to the player present at this counter. This player should choose a positive number of candies $M$ to accept, where $1 ≤ M ≤ C$.
If this player accepts an odd number of candies, the players have to swap their positions (each player goes to the other counter).
After each $N$ turns, the counter which was currently open is closed and the counter which was currently closed is opened.
The primary goal of each player is to maximise his own number of candies after $R$ turns. As a second priority, each player wants to minimise the number of candies his opponent has after $R$ turns.

You should process $Q$ queries. In each query, you are given $R$ and you should find the number of candies Chef has after $R$ turns, assuming that both players play the game optimally. Since this number could be very large, compute it 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 a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
The third line contains a single integer $Q$.
Each of the next $Q$ lines contains a single integer $R$ describing a query.

------  Output ------
For each query, print a single line containing one integer ― the maximum number of candies Chef can get, modulo $10^{9}+7$.

------  Constraints ------
$1 ≤ T ≤ 25$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
$A_{1}, A_{2}, \ldots, A_{N}$ are pairwise distinct
$1 ≤ Q ≤ 10^{5}$
$1 ≤ R ≤ 10^{12}$
the sum of $N + Q$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (15 points):
$N ≤ 10$
$Q ≤ 35$
$R ≤ 35$

Subtask #2 (85 points): original constraints

----- Sample Input 1 ------ 
1

4

4 10 2 1

2

4

5
----- Sample Output 1 ------ 
17

21
----- explanation 1 ------ 
Example case 1: In the $1$-st, $2$-nd and $3$-rd turn, Chef takes $4$, $10$ and $2$ candies ($16$ in total) respectively. In the $4$-th turn, Chef takes $1$ candy ($17$ in total; this is the answer to the first query), which is odd and hence he has to go to the counter which is closed. However, since $N = 4$ turns are just completed, the counter which was currently open closes and the other one (where Chef went) opens. In the $5$-th round, Chef can take $4$ candies, so he has $21$ candies.

Difficulty: HARD
Tags: Game theory

Range queries
Skill types: Range queries

Starter code:

Solutions:
from math import ceil
import sys
t = int(input())
mod = 10 ** 9 + 7
for ss in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	if n == 1:
		q = int(input())
		for i in range(q):
			r = int(input())
			if not a[0] % 2:
				print(((r - 1) * (a[0] - 1) + a[0]) % mod)
			else:
				print(r * a[0] % mod)
		continue
	if a[0] == 1:
		q = int(input())
		for i in range(q):
			r = int(input())
			if r != 1 and r % n == 1:
				print(r // n % mod)
			else:
				print(ceil(r / n) % mod)
		continue
	s = [a[i] for i in range(n)]
	if a[0] % 2:
		b.append(a[0] - 1)
	else:
		b.append(a[0])
	p = 0
	w = None
	for i in range(1, n - 1):
		if a[i] == 1:
			w = i
			a[i] = 0
			b.pop()
			if not s[i - 1] % 2:
				p = 1
				a[i - 1] -= 1
				b.append(s[i - 1] - 1)
			else:
				b.append(s[i - 1])
		elif a[i] % 2:
			a[i] -= 1
		b.append(a[i])
	if not a[n - 1] % 2:
		b.append(a[n - 1] - 1)
	else:
		b.append(a[n - 1])
	pre = [0 for i in range(n)]
	pre[0] = b[0]
	for i in range(1, n):
		pre[i] = pre[i - 1] + b[i]
	q = int(input())
	for i in range(q):
		r = int(input())
		ans = r // n * pre[n - 1]
		ans %= mod
		if r % n:
			ans += pre[r % n - 1]
			ans %= mod
		if w and r % n - 1 == w:
			if p:
				ans += 2
		elif w and r % n - 1 == w - 1:
			if p:
				ans += 1
		elif not r % n:
			if not s[n - 1] % 2:
				ans += 1
		elif s[r % n - 1] % 2:
			ans += 1
		if ans >= mod:
			ans -= mod
		print(ans % mod)


import math

def helper(n, l, q):
	mod = 10 ** 9 + 7
	if l[0] == 1:
		for i in q:
			ans = math.ceil(i / n)
			if i != 1 and i % n == 1:
				ans -= 1
			print(int(ans) % mod)
	else:
		pre = [0] * n
		ind = -1
		for i in range(n - 1):
			if l[i] == 1:
				ind = i
				break
		i = 0
		while i < n:
			pre[i] = pre[i - 1] % mod
			if i + 1 == ind:
				if l[i] % 2 == 1:
					pre[i] = (pre[i] % mod + l[i] % mod) % mod
				else:
					pre[i] = (pre[i] % mod + (l[i] - 1) % mod) % mod
				i += 1
				pre[i] = pre[i - 1]
			elif i == n - 1:
				if l[i] % 2 == 0:
					pre[i] = (pre[i] % mod + (l[i] - 1) % mod) % mod
				else:
					pre[i] = (pre[i] % mod + l[i] % mod) % mod
			elif l[i] % 2 == 1:
				pre[i] = (pre[i] % mod + (l[i] - 1) % mod) % mod
			else:
				pre[i] = (pre[i] % mod + l[i] % mod) % mod
			i += 1
		for i in q:
			rem = i % n
			ans = pre[-1] * (i // n) % mod
			if rem != 0:
				index = rem - 1
				if ind == -1:
					if l[index] % 2 == 1:
						ans += 1
				elif index == ind:
					if l[index - 1] % 2 == 0:
						ans += 2
				elif index + 1 == ind:
					if l[index] % 2 == 0:
						ans += 1
				elif index + 1 != ind:
					if l[index] % 2 == 1:
						ans += 1
				ans = (ans + pre[index]) % mod
			else:
				index = n - 1
				if l[index] % 2 == 0:
					ans += 1
			print(ans % mod)
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	q = []
	for i in range(int(input())):
		q.append(int(input()))
	helper(n, l, q)


import sys
MOD = pow(10, 9) + 7

def debug(*args):
	print(*args, file=sys.stderr)

def solve(A):
	N = len(A)
	solns = [0 for _ in range(N)]
	my_turn = True
	my_score = 0
	foe_score = 0
	if A[0] == 1:
		solns[0] = 1
	for i in range(N):
		even = A[i]
		odd = even - 1
		if even % 2:
			(even, odd) = (odd, even)
		if A[i] == 1:
			if my_turn:
				my_score = (my_score + 1) % MOD
			my_turn = not my_turn
		elif i == N - 2 and A[-1] == 1:
			if my_turn:
				solns[i] = (my_score + A[i]) % MOD
				solns[i + 1] = (my_score + even + 1) % MOD
				my_score = (my_score + even) % MOD
		elif i == N - 1:
			if my_turn:
				solns[i] = (my_score + A[i]) % MOD
				my_score = (my_score + odd) % MOD
				my_turn = not my_turn
		elif i < N - 1 and A[i + 1] == 1:
			if my_turn:
				solns[i] = (my_score + A[i]) % MOD
				solns[i + 1] = my_score + even + 1 % MOD
				my_score = (my_score + odd) % MOD
				my_turn = not my_turn
		elif my_turn:
			solns[i] = (my_score + A[i]) % MOD
			my_score = (my_score + even) % MOD
	return (my_score, solns)

def query(A, cycle_score, solns, R):
	N = len(A)
	if N == 1:
		even = A[0]
		odd = even - 1
		if even % 2:
			(even, odd) = (odd, even)
		soln = R * odd % MOD
		soln = (soln + A[0]) % MOD
		return soln
	M = R // N
	score = M * cycle_score
	if A[0] == 1:
		if R == 0 or R % N:
			score = (score + 1) % MOD
	else:
		score = score + solns[R % N]
	return score % MOD

def main():
	test_cases = int(sys.stdin.readline())
	for _ in range(test_cases):
		N = int(sys.stdin.readline())
		A = [int(i) for i in sys.stdin.readline().split()]
		(cycle_score, solns) = solve(A)
		Q = int(sys.stdin.readline())
		for q in range(Q):
			R = int(sys.stdin.readline())
			print(query(A, cycle_score, solns, R - 1))
main()


mod = 10 ** 9 + 7

def Retain(A):
	ln = len(A)
	re = 0
	if A[0] == 1:
		re = 1
	elif A[-1] == 1:
		for it in A[:-1]:
			re = re + it
			if it % 2:
				re -= 1
			re %= mod
		re += 1
	else:
		for (i, it) in enumerate(A[:-1]):
			re = re + it
			if i + 1 < ln and A[i + 1] == 1:
				if it % 2 == 0:
					re -= 1
			elif it % 2:
				re -= 1
			re %= mod
		re += A[-1]
		if A[-1] % 2 == 0:
			re -= 1
	re %= mod
	return re

def DontCare(A):
	dp = [0] * (len(A) + 1)
	if A[0] == 1:
		dp[1] = 0
		for i in range(2, len(A) + 1):
			dp[i] = 1
	elif A[-1] == 1:
		for (i, it) in enumerate(A[:-1]):
			dp[i + 1] += it
			dp[i + 2] = dp[i + 1]
			if it % 2:
				dp[i + 2] -= 1
			dp[i + 1] %= mod
		dp[-1] += 1
		dp[-1] %= mod
	else:
		dp[1] = A[0]
		for i in range(1, len(A)):
			it = A[i]
			if it == 1:
				dp[i + 1] = dp[i]
				if A[i - 1] % 2 == 0:
					dp[i + 1] += 1
			elif A[i - 1] == 1:
				dp[i + 1] = dp[i - 1] + it
				if A[i - 2] % 2 == 0:
					dp[i + 1] -= 1
			else:
				dp[i + 1] = dp[i] + it
				if A[i - 1] % 2:
					dp[i + 1] -= 1
			dp[i + 1] %= mod
	return dp
for case in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	Q = int(input())
	dp = DontCare(A)
	rt = Retain(A)
	for q in range(Q):
		R = int(input())
		ans = 0
		if R == 1:
			ans = A[0]
		else:
			r = R % n
			times = R // n
			if r:
				ans = rt * times % mod + dp[r]
			else:
				ans = rt * (times - 1) % mod + dp[n]
			if len(A) == 1 and A[0] == 1:
				ans = R
			ans %= mod
		print(ans)


def case1():
	pass

def case2():
	pass

def case3():
	pass
for _ in range(int(input())):
	mod = 1000000007
	c = -1
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(len(a)):
		if a[i] == 1:
			if i == 0:
				c = 0
			elif i != n - 1:
				c = i
	if c == 0:
		q = int(input())
		while q:
			r = int(input())
			if r % n == 0:
				print(r // n % mod)
			elif r % n == 1 and r > n:
				print(r // n % mod)
			else:
				print((r // n + 1) % mod)
			q -= 1
	elif c > 0:
		s = 0
		x = [0] * n
		for i in range(0, n - 1):
			if i == c - 1:
				if a[i] % 2 == 0:
					s += a[i] - 1
					x[i] = s
				else:
					s += a[i]
					x[i] = s
			elif a[i] % 2 == 0:
				s += a[i]
				x[i] = s
			else:
				s += a[i] - 1
				x[i] = s
		if a[n - 1] % 2 == 0:
			s += a[n - 1] - 1
		else:
			s += a[n - 1]
		q = int(input())
		while q:
			r = int(input())
			if r % n == 0:
				if a[n - 1] % 2 == 0:
					print((r // n * s + 1) % mod)
				else:
					print(r // n * s % mod)
			elif c == r % n - 1:
				if a[c - 1] % 2 == 0:
					print((r // n * s + x[r % n - 1] + 2) % mod)
				else:
					print((r // n * s + x[r % n - 1]) % mod)
			elif c - 1 == r % n - 1:
				if a[c - 1] % 2 == 0:
					print((r // n * s + x[r % n - 1] + 1) % mod)
				else:
					print((r // n * s + x[r % n - 1]) % mod)
			elif a[r % n - 1] % 2 != 0:
				print((r // n * s + x[r % n - 1] + 1) % mod)
			else:
				print((r // n * s + x[r % n - 1]) % mod)
			q -= 1
	else:
		s = 0
		x = [0] * n
		for i in range(0, n - 1):
			if a[i] % 2 == 1:
				s += a[i] - 1
				x[i] = s
			else:
				s += a[i]
				x[i] = s
		if a[n - 1] % 2 == 0:
			s += a[n - 1] - 1
		else:
			s += a[n - 1]
		q = int(input())
		while q:
			r = int(input())
			if r % n == 0:
				if a[n - 1] % 2 == 0:
					print((r // n * s + 1) % mod)
				else:
					print(r // n * s % mod)
			elif a[r % n - 1] % 2 != 0:
				print((r // n * s + x[r % n - 1] + 1) % mod)
			else:
				print((r // n * s + x[r % n - 1]) % mod)
			q -= 1


import sys
import math

def get_ints():
	return map(int, input().split())

def get_list():
	return list(map(int, input().split()))
MOD = int(1000000000.0 + 7)
for _ in range(int(input())):
	n = int(input())
	a = get_list()
	cnt = 0
	queries = int(input())
	ans = []
	if 1 in a:
		if a[0] == 1:
			for q in range(queries):
				r = int(input())
				cnt = r // n % MOD
				if r % n > 1 or r < n:
					cnt = (cnt + 1) % MOD
				print(cnt % MOD)
		elif a[-1] == 1:
			for i in range(n - 1):
				if a[i] % 2 == 1:
					cnt = (cnt + (a[i] - 1)) % MOD
				else:
					cnt = (cnt + a[i]) % MOD
				ans.append(cnt)
			cnt = (cnt + 1) % MOD
			ans.append(cnt)
			for i in range(queries):
				r = int(input())
				cnt1 = r // n * cnt % MOD
				if r % n != 0:
					cnt1 = cnt1 + ans[r % n - 1]
					if a[r % n - 1] & 1:
						cnt1 = (cnt1 + 1) % MOD
				print(cnt1 % MOD)
		else:
			cnt4 = 0
			cnt1 = 0
			idx = 0
			idx = a.index(1)
			for j in range(idx - 1):
				if a[j] & 1:
					cnt1 = (cnt1 + (a[j] - 1)) % MOD
				else:
					cnt1 = (cnt1 + a[j]) % MOD
				ans.append(cnt1)
			if a[idx - 1] & 1:
				cnt4 = (cnt1 + (a[idx - 1] - 1)) % MOD
				cnt1 = (cnt1 + a[idx - 1]) % MOD
			else:
				cnt4 = (cnt1 + a[idx - 1]) % MOD
				cnt1 = (cnt1 + (a[idx - 1] - 1)) % MOD
			ans.append(cnt1)
			ans.append(cnt4 + 1)
			for j in range(idx + 1, n - 1):
				if a[j] & 1:
					cnt1 = (cnt1 + (a[j] - 1)) % MOD
				else:
					cnt1 = (cnt1 + a[j]) % MOD
				ans.append(cnt1)
			if a[-1] & 1:
				cnt1 = (cnt1 + a[-1]) % MOD
			else:
				cnt1 = (cnt1 + (a[-1] - 1)) % MOD
			ans.append(cnt1)
			for i in range(queries):
				r = int(input())
				cnt = cnt1 * (r // n)
				cnt %= MOD
				md = r % n
				if md - 1 < idx:
					if md == 0:
						if a[-1] % 2 == 0:
							cnt = (cnt + 1) % MOD
					else:
						if md - 2 > -1:
							cnt = (cnt + ans[md - 2]) % MOD
						cnt = (cnt + a[md - 1]) % MOD
				elif md - 1 == idx:
					cnt = (cnt + ans[md - 1]) % MOD
				else:
					cnt = (cnt + ans[md - 1]) % MOD
					if a[md - 1] % 2 != 0:
						cnt = (cnt + 1) % MOD
				cnt %= MOD
				print(cnt)
	else:
		cnt = 0
		ans = []
		for j in range(n - 1):
			if a[j] & 1:
				cnt = (cnt + (a[j] - 1)) % MOD
			else:
				cnt = (cnt + a[j]) % MOD
			ans.append(cnt)
		if a[-1] & 1:
			cnt = (cnt + a[-1]) % MOD
			ans.append(cnt)
		else:
			cnt = (cnt + (a[-1] - 1)) % MOD
			ans.append(cnt)
		for i in range(queries):
			r = int(input())
			cnt1 = r // n * cnt % MOD
			md = r % n
			if md == 0:
				if a[-1] % 2 == 0:
					cnt1 = (cnt1 + 1) % MOD
			else:
				cnt1 = (cnt1 + ans[md - 1]) % MOD
				if a[md - 1] % 2 == 1:
					cnt1 = (cnt1 + 1) % MOD
			cnt1 %= MOD
			print(cnt1)


def solve(arr, n, q):
	mod = 10 ** 9 + 7
	result = 0
	if arr[0] == 1:
		for r in q:
			rem = r % n
			quo = r // n
			if r <= n:
				result = 1
			else:
				result = quo
				if rem != 0 and rem != 1:
					result += 1
			print(result % mod)
	else:
		ind = -1
		dp_arr = [0] * n
		for i in range(n):
			if arr[i] == 1:
				ind = i
				break
		if ind == -1 or ind == n - 1:
			s = 0
			for i in range(n):
				s += arr[i]
				if arr[i] % 2 != 0 and i != n - 1 or (i == n - 1 and arr[n - 1] % 2 == 0):
					s -= 1
				dp_arr[i] = s
			for r in q:
				quo = r // n
				rem = r % n
				sum_ = dp_arr[n - 1]
				result = quo * sum_
				if rem != 0 or result == 0:
					result += dp_arr[rem - 1]
				if arr[rem - 1] % 2 != 0 and rem != 0 or (rem == 0 and arr[n - 1] % 2 == 0):
					result += 1
				print(result % mod)
		else:
			s = 0
			for i in range(n):
				s += arr[i]
				if i != n - 1 and arr[i + 1] == 1:
					if arr[i] % 2 == 0:
						s -= 1
				elif arr[i] % 2 != 0 and i != n - 1 or (arr[i] % 2 == 0 and i == n - 1):
					s -= 1
				dp_arr[i] = s
			for r in q:
				quo = r // n
				rem = r % n
				sum_ = dp_arr[n - 1]
				result = quo * sum_
				if arr[n - 1] % 2 == 0 and rem == 0:
					result += 1
				elif rem != 0:
					result += dp_arr[rem - 1]
					if arr[rem - 1] % 2 != 0 and arr[rem] != 1 and (arr[rem - 1] != 1):
						result += 1
					elif arr[rem] == 1 and arr[rem - 1] % 2 == 0:
						result += 1
					elif arr[rem - 2] % 2 == 0 and arr[rem - 1] == 1:
						result += 2
				print(result % mod)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	q = [int(input()) for i in range(int(input()))]
	solve(arr, n, q)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = []
	b = []
	sum = 0
	res = 0
	a = list(map(int, input().strip().split()))[:n]
	for k in range(0, n):
		if k == 0 and a[k] == 1:
			res = 1
			break
		elif k == n - 1:
			if a[k] % 2 == 0:
				sum = sum + a[k] - 1
			else:
				sum = sum + a[k]
		elif a[k] == 1:
			sum = sum + 1
		elif a[k] % 2 == 0:
			sum = sum + a[k]
		else:
			sum = sum - 1 + a[k]
		if k > 1:
			if a[k - 1] == 1:
				if a[k - 2] % 2 == 0:
					sum = sum - 2
		b.insert(k, sum)
	q = int(input())
	for j in range(0, q):
		x = int(input())
		ans = 0
		z = x // n
		z1 = x % n
		if res == 1:
			if z1 == 0:
				ans = z
			else:
				ans = z + 1
			if z1 == 1 and x >= n + 1:
				ans = ans - 1
		elif z1 == 0:
			if a[n - 1] % 2 == 0:
				ans = ans + 1 + z * b[n - 1]
			else:
				ans = ans + z * b[n - 1]
		elif a[z1 - 1] % 2 == 0:
			ans = ans + z * b[n - 1] + b[z1 - 1]
		elif a[z1 - 1] != 1:
			ans = ans + z * b[n - 1] + b[z1 - 1] + 1
		else:
			ans = ans + z * b[n - 1] + b[z1 - 1]
		mod = 1000000007
		ans = ans % mod
		print(ans)


import sys

def boolean(n):
	return [0] * n

def update(l):
	for i in range(len(l) - 1):
		if l[i] != 1 and l[i] & 1:
			l[i] -= 1
	return l

def update2(l):
	d = boolean(n)
	d[0] = l[0]
	for i in range(1, len(l)):
		d[i] += l[i] + d[i - 1]
	return d
pakka = 10 ** 9 + 7
modulo = pakka

def check(l, p):
	for __ in range(int(sys.stdin.readline())):
		count = 0
		x = int(sys.stdin.readline())
		qestion = x // n
		reminder = x % n
		if reminder != 0:
			if reminder >= 2:
				count += p[reminder - 2] % pakka
				count = count % pakka
			count += t[reminder - 1] % pakka
			count = count % pakka
		elif l[-1] % 2 == 0:
			count += 1
			count = count % pakka
		if l[-1] & 1:
			count += p[n - 1] * qestion % pakka
			count = count % pakka
		else:
			count += (p[n - 1] * qestion % modulo - qestion) % pakka
			count = count % pakka
		print(count % pakka)

def check1(l, p, i):
	for __ in range(int(sys.stdin.readline())):
		c = 0
		x = int(sys.stdin.readline())
		reminder = x % n
		qestion = x // n
		c += p[n - 1] * qestion % pakka
		c = c % pakka
		if reminder != 0:
			if reminder >= 2:
				c += p[reminder - 2] % pakka
				c = c % pakka
			c += t[reminder - 1] % pakka
			c = c % pakka
		print(c % pakka)

def check2(l, p, i):
	for __ in range(int(sys.stdin.readline())):
		c = 0
		x = int(sys.stdin.readline())
		q = x // n
		r = x % n
		c += q % pakka
		c = c % pakka
		if x == 1:
			print(1)
			continue
		if r > 1:
			c += 1
			c = c % pakka
		print(c % pakka)

def che1ck(l, p, i):
	sum1 = p[n - 1]
	sum1 = sum1 % pakka
	if t[i - 1] & 1:
		sum1 += 1
		sum1 = sum1 % pakka
	for __ in range(int(sys.stdin.readline())):
		x = int(sys.stdin.readline())
		c = 0
		if x < i + 1:
			c += p[x - 1] % pakka
			if t[x - 1] & 1:
				c += 1 % pakka
				c = c % pakka
			print(c % pakka)
		elif x == i + 1:
			c += p[x - 1] % pakka
			print(c % pakka)
		else:
			qestion = x // n
			reminder = x % n
			c += (qestion * sum1 % pakka - qestion) % pakka
			if l[-1] % 2 == 0:
				c -= qestion % pakka
			if t[i - 1] % 2 == 0:
				c -= qestion % pakka
			if reminder != 0:
				if reminder <= i + 1:
					if reminder >= 2:
						c += p[reminder - 2] % pakka
						c = c % pakka
					c += t[reminder - 1] % pakka
					c = c % pakka
				else:
					if i >= 2:
						c += p[i - 2]
					if t[i - 1] % 2 == 1:
						c += t[i - 1] % pakka
						c = c % pakka
					else:
						c += t[i - 1] - 1
						c = c % pakka
					c += (p[reminder - 2] - p[i]) % pakka
					c = c % pakka
					c += t[reminder - 1] % pakka
					c = c % pakka
			elif l[-1] % 2 == 0:
				c += 1
				c = c % pakka
			print(c % pakka)
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	l = list(map(int, input().split()))
	t = l.copy()
	l = update(l)
	p = update2(l)
	if 1 not in l:
		check(l, p)
	else:
		i = l.index(1)
		if i == n - 1:
			check1(l, p, i)
		elif i == 0:
			check2(l, p, i)
		else:
			che1ck(l, p, i)


def krokro():
	n = int(input())
	l = [int(x) for x in input().split()]
	m = 10 ** 9 + 7
	ar = [0 for x in range(n)]
	for i in range(n):
		if l[i] % 2 == 0:
			ar[i] = l[i] % m
		else:
			ar[i] = (l[i] - 1) % m
	pre = [0 for x in range(n)]
	pre[0] = ar[0]
	for i in range(1, n):
		pre[i] = (pre[i - 1] + ar[i]) % m
	if n == 1:
		for i in range(int(input())):
			r = int(input())
			if l[0] % 2 == 0:
				ans = (l[0] - 1) * (r - 1) + l[0]
			else:
				ans = l[0] * r
			print(ans % m)
	elif 1 in l:
		if l[0] == 1:
			for i in range(int(input())):
				r = int(input())
				if r == 1:
					ans = 1
				elif r % n > 1:
					ans = r // n + 1
				else:
					ans = r // n
				print(ans % m)
		elif l[n - 1] == 1:
			for i in range(int(input())):
				r = int(input())
				if r == 1:
					ans = l[0]
				elif r <= n:
					ans = pre[r - 2] + l[r - 1]
				elif r % n == 0:
					ans = (pre[n - 1] + 1) * (r // n)
				elif r % n == 1:
					ans = (pre[n - 1] + 1) * (r // n) + l[0]
				else:
					f = r % n
					ans = (pre[n - 1] + 1) * (r // n) + pre[f - 2] + l[f - 1]
				print(ans % m)
		else:
			ind = l.index(1)
			if l[ind - 1] % 2 == 0:
				for i in range(int(input())):
					r = int(input())
					if r == 1:
						ans = l[0]
					elif r <= n:
						if r <= ind + 1:
							ans = pre[r - 2] + l[r - 1]
						elif ind == 1:
							ans = l[0] - 1 + (pre[r - 2] - pre[ind]) + l[r - 1]
						else:
							ans = pre[ind - 2] + l[ind - 1] - 1 + pre[r - 2] - pre[ind] + l[r - 1]
					elif r % n == 0:
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
								ans = temp * (r // n - 1) + (temp + 1)
							else:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
								ans = temp * (r // n)
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
							ans = temp * (r // n - 1) + (temp + 1)
						else:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
							ans = temp * (r // n)
					elif r % n == 1:
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
								ans = temp * (r // n) + l[0]
							else:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
								ans = temp * (r // n) + l[0]
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
							ans = temp * (r // n) + l[0]
						else:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
							ans = temp * (r // n) + l[0]
					else:
						f = r % n
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
								if f == 1:
									ans = temp * (r // n) + l[0]
								elif f == 2:
									ans = temp * (r // n) + l[0] + l[ind]
								else:
									ans = temp * (r // n) + l[ind - 1] - 1 + pre[f - 2] - pre[ind] + l[f - 1]
							else:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
								if f == 1:
									ans = temp * (r // n) + l[0]
								elif f <= ind + 1:
									ans = temp * (r // n) + l[0] + l[ind]
								else:
									ans = temp * (r // n) + l[ind - 1] - 1 + pre[f - 2] - pre[ind] + l[f - 1]
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
							if f == 1:
								ans = temp * (r // n) + l[0]
							if f <= ind + 1:
								ans = temp * (r // n) + pre[f - 2] + l[f - 1]
							else:
								ans = temp * (r // n) + pre[ind - 2] + l[ind - 1] - 1 + pre[f - 2] - pre[ind] + l[f - 1]
						else:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
							if f <= ind + 1:
								ans = temp * (r // n) + pre[f - 2] + l[f - 1]
							else:
								ans = temp * (r // n) + pre[ind - 2] + l[ind - 1] - 1 + (pre[f - 2] - pre[ind]) + l[f - 1]
					print(ans % m)
			else:
				for i in range(int(input())):
					r = int(input())
					if r == 1:
						ans = l[0]
					elif r <= n:
						if r <= ind + 1:
							ans = pre[r - 2] + l[r - 1]
						elif ind == 1:
							ans = l[0] + pre[r - 2] - pre[ind] + l[r - 1]
						else:
							ans = pre[ind - 2] + l[ind - 1] + pre[r - 2] - pre[ind] + l[r - 1]
					elif r % n == 0:
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1] - 1
								ans = temp * (r // n) + 1
							else:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1]
								ans = temp * (r // n)
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1] - 1
							ans = temp * (r // n) + 1
						else:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1]
							ans = temp * (r // n)
					elif r % n == 1:
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1] - 1
								ans = temp * (r // n) + l[0]
							else:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1]
								ans = temp * (r // n) + l[0]
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1] - 1
							ans = temp * (r // n) + l[0]
						else:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1]
							ans = temp * (r // n) + l[0]
					else:
						f = r % n
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1] - 1
								if f == 2:
									ans = temp * (r // n) + l[0]
								else:
									ans = temp * (r // n) + l[0] + pre[f - 2] - pre[ind] + l[f - 1]
							else:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1]
								if f == 2:
									ans = temp * (r // n) + l[0]
								else:
									ans = temp * (r // n) + l[0] + pre[f - 2] - pre[ind] + l[f - 1]
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1] - 1
							if f <= ind + 1:
								ans = temp * (r // n) + pre[f - 2] + l[f - 1]
							else:
								ans = temp * (r // n) + pre[ind - 2] + l[ind - 1] + pre[f - 2] - pre[ind] + l[f - 1]
						else:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1]
							if f <= ind + 1:
								ans = temp * (r // n) + pre[f - 2] + l[f - 1]
							else:
								ans = temp * (r // n) + pre[ind - 2] + l[ind - 1] + pre[f - 2] - pre[ind] + l[f - 1]
					print(ans % m)
	else:

		def noone():
			for i in range(int(input())):
				r = int(input())
				if r == 1:
					ans = l[0]
				elif r <= n:
					ans = pre[r - 2] + l[r - 1]
				elif l[n - 1] % 2 == 0:
					temp = pre[n - 2] + l[n - 1] - 1
					if r % n == 0:
						ans = temp * (r // n) + 1
					else:
						f = r % n
						if f == 1:
							ans = temp * (r // n) + l[0]
						else:
							ans = temp * (r // n) + pre[f - 2] + l[f - 1]
				else:
					temp = pre[n - 2] + l[n - 1]
					if r % n == 0:
						ans = temp * (r // n)
					else:
						f = r % n
						if f == 1:
							ans = temp * (r // n) + l[0]
						else:
							ans = temp * (r // n) + pre[f - 2] + l[f - 1]
				print(ans % m)
		noone()
for _ in range(int(input())):
	krokro()


from math import ceil

def find(l):
	for i in range(len(l) - 1):
		if l[i] == 1:
			return i
	return -1

def solve(n, l, q):
	mod = 10 ** 9 + 7
	if l[0] == 1:
		for i in q:
			ans = ceil(i / n)
			if i != 1 and i % n == 1:
				ans -= 1
			print(int(ans) % mod)
	else:
		pre = [0] * n
		ind = find(l)
		i = 0
		while i < n:
			pre[i] = pre[i - 1] % mod
			if i + 1 == ind:
				if l[i] % 2 == 1:
					pre[i] = (pre[i] % mod + l[i] % mod) % mod
				else:
					pre[i] = (pre[i] % mod + (l[i] - 1) % mod) % mod
				i += 1
				pre[i] = pre[i - 1]
			elif i == n - 1:
				if l[i] % 2 == 0:
					pre[i] = (pre[i] % mod + (l[i] - 1) % mod) % mod
				else:
					pre[i] = (pre[i] % mod + l[i] % mod) % mod
			elif l[i] % 2 == 1:
				pre[i] = (pre[i] % mod + (l[i] - 1) % mod) % mod
			else:
				pre[i] = (pre[i] % mod + l[i] % mod) % mod
			i += 1
		for i in q:
			rem = i % n
			ans = pre[-1] * (i // n) % mod
			if rem != 0:
				index = rem - 1
				if ind == -1:
					if l[index] % 2 == 1:
						ans += 1
				elif index == ind:
					if l[index - 1] % 2 == 0:
						ans += 2
				elif index + 1 == ind:
					if l[index] % 2 == 0:
						ans += 1
				elif index + 1 != ind:
					if l[index] % 2 == 1:
						ans += 1
				ans = (ans + pre[index]) % mod
			else:
				index = n - 1
				if l[index] % 2 == 0:
					ans += 1
			print(ans % mod)
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	q = []
	for i in range(int(input())):
		q.append(int(input()))
	solve(n, l, q)


mod = 1000000000.0 + 7
test = int(input())
while test:
	n = int(input())
	arr = [int(x) for x in input().split()]
	qry = int(input())
	M = int(1000000000.0 + 7)
	ans = []
	if 1 in arr:
		if arr[0] == 1:
			for i in range(qry):
				qq = int(input())
				cnt = qq // n % M
				if qq % n > 1 or qq < n:
					cnt = (cnt + 1) % M
				print(cnt % M)
		elif arr[-1] == 1:
			cnt = 0
			for i in range(n - 1):
				if arr[i] % 2 == 1:
					cnt = (cnt + (arr[i] - 1)) % M
				else:
					cnt = (cnt + arr[i]) % M
				ans.append(cnt)
			cnt = (cnt + 1) % M
			ans.append(cnt)
			for i in range(qry):
				qq = int(input())
				cnt1 = qq // n * cnt % M
				md = qq % n
				if md != 0:
					cnt1 = cnt1 + ans[md - 1]
					if arr[md - 1] & 1:
						cnt1 = (cnt1 + 1) % M
				print(cnt1 % M)
		else:
			idx = 0
			idx = arr.index(1)
			cnt1 = 0
			cnt4 = 0
			for j in range(idx - 1):
				if arr[j] & 1:
					cnt1 = (cnt1 + (arr[j] - 1)) % M
				else:
					cnt1 = (cnt1 + arr[j]) % M
				ans.append(cnt1)
			if arr[idx - 1] & 1:
				cnt4 = (cnt1 + (arr[idx - 1] - 1)) % M
				cnt1 = (cnt1 + arr[idx - 1]) % M
			else:
				cnt4 = (cnt1 + arr[idx - 1]) % M
				cnt1 = (cnt1 + (arr[idx - 1] - 1)) % M
			ans.append(cnt1)
			ans.append(cnt4 + 1)
			for j in range(idx + 1, n - 1):
				if arr[j] & 1:
					cnt1 = (cnt1 + (arr[j] - 1)) % M
				else:
					cnt1 = (cnt1 + arr[j]) % M
				ans.append(cnt1)
			if arr[-1] & 1:
				cnt1 = (cnt1 + arr[-1]) % M
			else:
				cnt1 = (cnt1 + (arr[-1] - 1)) % M
			ans.append(cnt1)
			for i in range(qry):
				qq = int(input())
				cnt = cnt1 * (qq // n)
				cnt %= M
				md = qq % n
				if md - 1 < idx:
					if md == 0:
						if arr[-1] % 2 == 0:
							cnt = (cnt + 1) % M
					else:
						if md - 2 > -1:
							cnt = (cnt + ans[md - 2]) % M
						cnt = (cnt + arr[md - 1]) % M
				elif md - 1 == idx:
					cnt = (cnt + ans[md - 1]) % M
				else:
					cnt = (cnt + ans[md - 1]) % M
					if arr[md - 1] % 2 != 0:
						cnt = (cnt + 1) % M
				cnt %= M
				print(cnt)
	else:
		cnt = 0
		ans = []
		for j in range(n - 1):
			if arr[j] & 1:
				cnt = (cnt + (arr[j] - 1)) % M
			else:
				cnt = (cnt + arr[j]) % M
			ans.append(cnt)
		if arr[-1] & 1:
			cnt = (cnt + arr[-1]) % M
			ans.append(cnt)
		else:
			cnt = (cnt + (arr[-1] - 1)) % M
			ans.append(cnt)
		for i in range(qry):
			qq = int(input())
			cnt1 = qq // n * cnt % M
			md = qq % n
			if md == 0:
				if arr[-1] % 2 == 0:
					cnt1 = (cnt1 + 1) % M
			else:
				cnt1 = (cnt1 + ans[md - 1]) % M
				if arr[md - 1] % 2 == 1:
					cnt1 = (cnt1 + 1) % M
			cnt1 %= M
			print(cnt1)
	test -= 1


def throw(n):
	print(n)

def numberinput():
	return int(input())

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

def vahankrsolve():
	n = numberinput()
	l = listinput()
	m = 10 ** 9 + 7
	ar = [0 for x in range(n)]
	for i in range(n):
		if l[i] % 2 == 0:
			ar[i] = l[i] % m
		else:
			ar[i] = (l[i] - 1) % m
	pre = [0 for x in range(n)]
	pre[0] = ar[0]
	for i in range(1, n):
		pre[i] = (pre[i - 1] + ar[i]) % m
	if n == 1:
		for i in range(int(input())):
			r = int(input())
			if l[0] % 2 == 0:
				ans = (l[0] - 1) * (r - 1) + l[0]
			else:
				ans = l[0] * r
			throw(ans % m)
	elif 1 in l:
		if l[0] == 1:
			for i in range(int(input())):
				r = int(input())
				if r == 1:
					ans = 1
				elif r % n > 1:
					ans = r // n + 1
				else:
					ans = r // n
				throw(ans % m)
		elif l[n - 1] == 1:
			for i in range(int(input())):
				r = int(input())
				if r == 1:
					ans = l[0]
				elif r <= n:
					ans = pre[r - 2] + l[r - 1]
				elif r % n == 0:
					ans = (pre[n - 1] + 1) * (r // n)
				elif r % n == 1:
					ans = (pre[n - 1] + 1) * (r // n) + l[0]
				else:
					f = r % n
					ans = (pre[n - 1] + 1) * (r // n) + pre[f - 2] + l[f - 1]
				throw(ans % m)
		else:
			ind = l.index(1)
			if l[ind - 1] % 2 == 0:
				for i in range(int(input())):
					r = int(input())
					if r == 1:
						ans = l[0]
					elif r <= n:
						if r <= ind + 1:
							ans = pre[r - 2] + l[r - 1]
						elif ind == 1:
							ans = l[0] - 1 + (pre[r - 2] - pre[ind]) + l[r - 1]
						else:
							ans = pre[ind - 2] + l[ind - 1] - 1 + pre[r - 2] - pre[ind] + l[r - 1]
					elif r % n == 0:
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
								ans = temp * (r // n - 1) + (temp + 1)
							else:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
								ans = temp * (r // n)
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
							ans = temp * (r // n - 1) + (temp + 1)
						else:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
							ans = temp * (r // n)
					elif r % n == 1:
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
								ans = temp * (r // n) + l[0]
							else:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
								ans = temp * (r // n) + l[0]
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
							ans = temp * (r // n) + l[0]
						else:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
							ans = temp * (r // n) + l[0]
					else:
						f = r % n
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
								if f == 1:
									ans = temp * (r // n) + l[0]
								elif f == 2:
									ans = temp * (r // n) + l[0] + l[ind]
								else:
									ans = temp * (r // n) + l[ind - 1] - 1 + pre[f - 2] - pre[ind] + l[f - 1]
							else:
								temp = l[0] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
								if f == 1:
									ans = temp * (r // n) + l[0]
								elif f <= ind + 1:
									ans = temp * (r // n) + l[0] + l[ind]
								else:
									ans = temp * (r // n) + l[ind - 1] - 1 + pre[f - 2] - pre[ind] + l[f - 1]
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1] - 1
							if f == 1:
								ans = temp * (r // n) + l[0]
							if f <= ind + 1:
								ans = temp * (r // n) + pre[f - 2] + l[f - 1]
							else:
								ans = temp * (r // n) + pre[ind - 2] + l[ind - 1] - 1 + pre[f - 2] - pre[ind] + l[f - 1]
						else:
							temp = pre[ind - 2] + l[ind - 1] - 1 + pre[n - 2] - pre[ind] + l[n - 1]
							if f <= ind + 1:
								ans = temp * (r // n) + pre[f - 2] + l[f - 1]
							else:
								ans = temp * (r // n) + pre[ind - 2] + l[ind - 1] - 1 + (pre[f - 2] - pre[ind]) + l[f - 1]
					throw(ans % m)
			else:
				for i in range(int(input())):
					r = int(input())
					if r == 1:
						ans = l[0]
					elif r <= n:
						if r <= ind + 1:
							ans = pre[r - 2] + l[r - 1]
						elif ind == 1:
							ans = l[0] + pre[r - 2] - pre[ind] + l[r - 1]
						else:
							ans = pre[ind - 2] + l[ind - 1] + pre[r - 2] - pre[ind] + l[r - 1]
					elif r % n == 0:
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1] - 1
								ans = temp * (r // n) + 1
							else:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1]
								ans = temp * (r // n)
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1] - 1
							ans = temp * (r // n) + 1
						else:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1]
							ans = temp * (r // n)
					elif r % n == 1:
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1] - 1
								ans = temp * (r // n) + l[0]
							else:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1]
								ans = temp * (r // n) + l[0]
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1] - 1
							ans = temp * (r // n) + l[0]
						else:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1]
							ans = temp * (r // n) + l[0]
					else:
						f = r % n
						if ind == 1:
							if l[n - 1] % 2 == 0:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1] - 1
								if f == 2:
									ans = temp * (r // n) + l[0]
								else:
									ans = temp * (r // n) + l[0] + pre[f - 2] - pre[ind] + l[f - 1]
							else:
								temp = l[0] + pre[n - 2] - pre[ind] + l[n - 1]
								if f == 2:
									ans = temp * (r // n) + l[0]
								else:
									ans = temp * (r // n) + l[0] + pre[f - 2] - pre[ind] + l[f - 1]
						elif l[n - 1] % 2 == 0:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1] - 1
							if f <= ind + 1:
								ans = temp * (r // n) + pre[f - 2] + l[f - 1]
							else:
								ans = temp * (r // n) + pre[ind - 2] + l[ind - 1] + pre[f - 2] - pre[ind] + l[f - 1]
						else:
							temp = pre[ind - 2] + l[ind - 1] + pre[n - 2] - pre[ind] + l[n - 1]
							if f <= ind + 1:
								ans = temp * (r // n) + pre[f - 2] + l[f - 1]
							else:
								ans = temp * (r // n) + pre[ind - 2] + l[ind - 1] + pre[f - 2] - pre[ind] + l[f - 1]
					throw(ans % m)
	else:
		for i in range(int(input())):
			r = int(input())
			if r == 1:
				ans = l[0]
			elif r <= n:
				ans = pre[r - 2] + l[r - 1]
			elif l[n - 1] % 2 == 0:
				temp = pre[n - 2] + l[n - 1] - 1
				if r % n == 0:
					ans = temp * (r // n) + 1
				else:
					f = r % n
					if f == 1:
						ans = temp * (r // n) + l[0]
					else:
						ans = temp * (r // n) + pre[f - 2] + l[f - 1]
			else:
				temp = pre[n - 2] + l[n - 1]
				if r % n == 0:
					ans = temp * (r // n)
				else:
					f = r % n
					if f == 1:
						ans = temp * (r // n) + l[0]
					else:
						ans = temp * (r // n) + pre[f - 2] + l[f - 1]
			throw(ans % m)
for testcase in range(int(input())):
	vahankrsolve()


for test in range(int(input())):
	num = int(input())
	arr = [int(x) for x in input().split()]
	cupid = int(input())
	run = list()
	for i in range(cupid):
		run.append(int(input()))
	answer = []
	key = False
	for i in range(num):
		if i == 0 and arr[i] == 1:
			answer.append(1)
			key = True
		elif key:
			answer.append(0)
		elif i + 1 > 0 and i + 1 < num - 1 and (arr[i + 1] == 1):
			if arr[i] % 2 == 0:
				answer.append(arr[i] - 1)
			else:
				answer.append(arr[i])
		elif i + 1 == num - 1 and arr[i + 1] == 1:
			if arr[i] % 2 == 0:
				answer.append(arr[i])
			else:
				answer.append(arr[i] - 1)
		elif i == num - 1:
			if arr[i] % 2 == 0:
				answer.append(arr[i] - 1)
			else:
				answer.append(arr[i])
		elif arr[i] % 2 == 0:
			answer.append(arr[i])
		else:
			answer.append(arr[i] - 1)
	cookup = list()
	temp = 0
	for i in range(num):
		temp = (temp + answer[i]) % (10 ** 9 + 7)
		cookup.append(temp)
	for i in range(cupid):
		if run[i] <= num:
			result = cookup[run[i] - 1]
			if not key:
				result = (result - answer[run[i] - 1] + arr[run[i] - 1]) % (10 ** 9 + 7)
				if arr[run[i] - 1] == 1 and arr[run[i] - 2] % 2 == 0 and (run[i] != num):
					result = (result + 1) % (10 ** 9 + 7)
				elif arr[run[i] - 1] == 1 and arr[run[i] - 2] % 2 == 1 and (run[i] != num):
					result = result - 1
			print(result)
		else:
			result = cookup[num - 1] * (run[i] // num % (10 ** 9 + 7))
			result = result % (10 ** 9 + 7)
			if run[i] % num != 0:
				result = (result + cookup[run[i] % num - 1]) % (10 ** 9 + 7)
			if not key:
				result = (result - answer[run[i] % num - 1] + arr[run[i] % num - 1]) % (10 ** 9 + 7)
				if arr[run[i] % num - 1] == 1 and arr[run[i] % num - 2] % 2 == 0 and (run[i] % num != 0):
					result = (result + 1) % (10 ** 9 + 7)
				elif arr[run[i] % num - 1] == 1 and arr[run[i] % num - 2] % 2 == 1 and (run[i] % num != 0):
					result = result - 1
			if key and run[i] % num == 1:
				result = result - 1
			print(result)


try:
	for ii in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		if a[0] == 1:
			q = int(input())
			for jj in range(q):
				r = int(input())
				if r != 1:
					d = r // n
					if d * n + 1 == r:
						r -= 1
					d = r // n
					if r % n == 0:
						print(d % 1000000007)
					else:
						print((d + 1) % 1000000007)
				else:
					print(1)
		else:
			p = []
			for jj in range(n - 1):
				if a[jj + 1] == 1:
					if a[jj] % 2 == 1:
						p.append(a[jj])
					else:
						p.append(a[jj] - 1)
				elif a[jj] % 2 == 1:
					p.append(a[jj] - 1)
				else:
					p.append(a[jj])
			p.append(0)
			if n != 1:
				if a[n - 2] % 2 == 1:
					p[n - 2] = a[n - 2] - 1
				else:
					p[n - 2] = a[n - 2]
			if a[n - 1] % 2 == 1:
				p[n - 1] = a[n - 1]
			else:
				p[n - 1] = a[n - 1] - 1
			t = p[:]
			for jj in range(1, n):
				p[jj] = p[jj] + p[jj - 1] % 1000000007
			q = int(input())
			for jj in range(q):
				r = int(input())
				(d, rem) = (r // n, r % n)
				ans = d * p[n - 1] % 1000000007
				if rem == 0:
					ans = (ans + abs((a[n - 1] - t[n - 1]) % 1000000007)) % 1000000007
				else:
					ans = (ans + p[rem - 1]) % 1000000007
					if a[rem - 1] == 1:
						if a[rem - 2] % 2 == 0:
							ans = (ans + 2) % 1000000007
					else:
						ans = (abs((a[rem - 1] - t[rem - 1]) % 1000000007) + ans) % 1000000007
				print(ans % 1000000007)
except:
	pass


from collections import defaultdict as dd
from operator import ior
from sys import stdin, stdout
import math

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
try:
	for t in range(int(stdin.readline().strip())):
		n = int(stdin.readline().strip())
		l = list(map(int, stdin.readline().strip().split()))
		flag = 0
		inc = 0
		modulus = 1000000007
		D = dd(lambda : 0)
		if l[0] == 1 and n > 1:
			flag = 1
		else:
			for i in range(n - 1):
				if l[i] == 1:
					if l[i - 1] % 2 == 1:
						D[i] = D[i - 1]
					else:
						D[i] = D[i - 1] + 1
				elif l[i + 1] == 1 and i < n - 2:
					if l[i] % 2 == 1:
						inc = inc + l[i]
						D[i] = inc
					else:
						D[i] = inc + l[i]
						inc += l[i] - 1
				elif l[i] % 2 == 1:
					D[i] = inc + l[i]
					inc += l[i] - 1
				else:
					inc = inc + l[i]
					D[i] = inc
			if l[n - 1] % 2 == 1:
				inc = inc + l[n - 1]
				D[n - 1] = inc
			else:
				D[n - 1] = inc + l[n - 1]
				inc += l[n - 1] - 1
		q = int(stdin.readline().strip())
		for i in range(q):
			r = int(stdin.readline().strip())
			quot = r // n
			remainder = r % n
			if flag == 1:
				if quot == 0 and remainder == 1:
					print(1)
					continue
				if remainder > 1:
					print((quot + 1) % modulus)
				else:
					print(quot % modulus)
				continue
			if quot == 0:
				print(D[remainder - 1] % modulus)
			elif remainder == 0:
				print(((quot - 1) * inc + D[n - 1]) % modulus)
			else:
				print((quot * inc + D[remainder - 1]) % modulus)
except:
	pass


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	data = list(map(int, input().split()))
	n = len(data)
	ans1 = ans2 = ans3 = ans4 = case = 0
	lastone = -1
	for i in range(n):
		if data[i] == 1:
			lastone = i
			case = data[i]
	if case:
		if 1 not in (data[-1], data[0]):
			case = 1
			for i in range(lastone - 1):
				ans1 += MOD + data[i] - 1 if data[i] & 1 else data[i]
			ans1 += data[lastone - 1] if data[lastone - 1] & 1 else MOD + data[lastone - 1] - 1
			for i in range(lastone + 1, n - 1):
				ans1 += MOD + data[i] - 1 if data[i] & 1 else data[i]
			ans1 += data[n - 1] if data[n - 1] & 1 else MOD + data[n - 1] - 1
			ans1 %= MOD
		elif data[0] == 1:
			case = 2
			ans2 = 1
		elif data[-1] == 1:
			case = 3
			for i in range(n - 1):
				ans3 += MOD + data[i] - 1 if data[i] & 1 else data[i]
			ans3 += 1
			ans3 %= MOD
	else:
		case = 4
		for i in range(n - 1):
			ans4 += MOD + data[i] - 1 if data[i] & 1 else data[i]
		ans4 += data[n - 1] if data[n - 1] & 1 else MOD + data[n - 1] - 1
		ans4 %= MOD
	ans = [0] * n
	dp = [0] * n
	rcount = [0] * n
	for i in range(n):
		if data[i] & 1:
			rcount[i] += 1
	for i in range(1, n):
		rcount[i] += rcount[i - 1]
	if case in (1, 3, 4):
		for i in range(n):
			ans[i] = data[i] if i == 0 else ans[i - 1] + data[i]
		dp[0] = ans[0]
		for i in range(1, n):
			dp[i] = (ans[i - 1] - rcount[i - 1] + data[i] + MOD) % MOD
			if i > lastone and lastone != -1:
				dp[i] += 1 if data[lastone - 1] & 1 else -1
			dp[i] %= MOD
	for q in range(int(input())):
		r = int(input())
		quo = (r - 1) // n
		rem = r - quo * n - 1
		final = 0
		if case in (1, 3, 4):
			final = dp[rem] % MOD
			final += quo * (ans1 if case == 1 else ans3 if case == 3 else ans4) % MOD
		else:
			final = r // n
			if r % n:
				final += 1
				if r % n - 1 == lastone and r // n > 0:
					final += -1 + MOD
		print((final + MOD) % MOD)


def middle(arr, n, result):
	f = False
	result[1] = arr[0]
	for i in range(1, n):
		result[i + 1] = result[i] + arr[i]
		if arr[i - 1] % 2 != 0:
			result[i + 1] -= 1
		if f == True:
			if arr[i - 2] % 2 != 0:
				result[i + 1] += 1
			else:
				result[i + 1] -= 1
			f = False
		if arr[i] == 1:
			f = True
	return result

def last(arr, n, result):
	result[1] = arr[0]
	for i in range(1, n - 1):
		result[i + 1] = result[i] + arr[i]
		if arr[i - 1] % 2 != 0:
			result[i + 1] = result[i + 1] - 1
	if n > 1:
		result[n] = result[n - 1] + arr[n - 1]
	if arr[n - 2] % 2 != 0:
		result[n] -= 1
	return result
mod = 1000000007
test = int(input())
for i in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	result = [0 for _ in range(n + 1)]
	if arr[n - 1] == 1:
		result = last(arr, n, result)
	elif arr[0] != 1:
		result = middle(arr, n, result)
	q = int(input())
	for i in range(q):
		r = int(input())
		ind = r // n
		ans = 0
		if n == 1:
			if arr[0] % 2 == 0:
				ans = (arr[0] - 1) % mod * (r - 1) % mod % mod
				ans = (ans % mod + arr[0] % mod) % mod
			else:
				ans = arr[0] % mod * r % mod % mod
		elif arr[0] == 1:
			if r <= n:
				ans = 1
			elif r % n == 1 or r % n == 0:
				ans = ind % mod
			elif r > n:
				ans = (ind % mod + 1) % mod
		elif arr[n - 1] == 1:
			ans = ind % mod * result[n] % mod % mod
			p = int(r % mod - ind % mod * n % mod) % mod
			ans = (ans % mod + result[p] % mod) % mod
		else:
			ans = ind % mod * result[n] % mod % mod
			if arr[n - 1] % 2 == 0:
				if r % n == 0:
					ans = (ans % mod - (ind - 1) % mod) % mod
				else:
					ans = (ans % mod - ind % mod) % mod
			p = int(r % mod - ind % mod * n % mod) % mod
			ans = (ans % mod + result[p] % mod) % mod
		print(ans)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	last_round = [0] * (n + 1)
	q = int(input())
	isOneInBeetween = False
	for i in range(1, n + 1):
		if a[i] == 1:
			isOneInBeetween = True
			break
	if a[1] != 1:
		if not isOneInBeetween or a[n] == 1:
			for i in range(1, n + 1):
				if i > 1 and a[i - 1] & 1 == 1:
					last_round[i] = ((last_round[i - 1] - 1) % mod + a[i]) % mod
				else:
					last_round[i] = (last_round[i - 1] + a[i]) % mod
		else:
			for i in range(1, n + 1):
				if i > 1:
					if a[i] == 1 and a[i - 1] & 1 == 0:
						last_round[i] = (last_round[i - 1] + 1) % mod
					elif a[i - 1] == 1 and a[i - 2] & 1 == 0:
						last_round[i] = ((last_round[i - 2] - 1) % mod + a[i]) % mod
					elif a[i - 1] & 1 == 1 and a[i - 1] != 1:
						last_round[i] = ((last_round[i - 1] - 1) % mod + a[i]) % mod
					else:
						last_round[i] = (last_round[i - 1] + a[i]) % mod
				else:
					last_round[i] = a[i] % mod
	for i in range(q):
		r = int(input())
		if r == 1:
			print(a[1] % mod)
			continue
		if n == 1:
			if a[1] & 1 == 0:
				ans = (r - 1) % mod * ((a[1] - 1) % mod) % mod
			else:
				ans = (r - 1) % mod * (a[1] % mod)
			ans = (ans + a[1] % mod) % mod
			print(ans % mod)
			continue
		if a[1] == 1:
			ans = r % mod // (n % mod) % mod
			if r % n != 0 and r % n != 1:
				ans = (ans + 1) % mod
			print(ans)
			continue
		if a[n] & 1 == 1:
			ans = last_round[n] % mod * (r % mod // (n % mod)) % mod
		else:
			ans = (last_round[n] - 1) % mod * (r % mod // (n % mod)) % mod
		j = r % n
		if j == 0:
			if a[n] & 1 == 0:
				ans = (ans + 1) % mod
		else:
			ans = (ans + last_round[j]) % mod
		print(ans)


from math import ceil
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	for_once = 0
	if a[0] != 1:
		for i in range(n):
			if i != n - 1:
				if a[i + 1] != 1 or i + 1 == n - 1:
					if a[i] % 2 == 0:
						for_once += a[i]
					else:
						for_once += a[i] - 1
				elif a[i + 1] == 1:
					if a[i] % 2 == 0:
						for_once += a[i] - 1
					else:
						for_once += a[i]
			elif i == n - 1:
				if a[i] % 2 == 1:
					for_once += a[i]
				else:
					for_once += a[i] - 1
	elif a[0] == 1:
		for_once = 1
	prefix = [0 for i in range(n)]
	cur = 0
	if a[0] != 1:
		for i in range(n):
			prefix[i] = cur + a[i]
			if i != n - 1:
				if a[i] == 1:
					if a[i - 1] % 2 == 0:
						prefix[i] = prefix[i - 1] + 1
					else:
						prefix[i] = prefix[i - 1]
				elif a[i + 1] != 1 or i + 1 == n - 1:
					if a[i] % 2 == 0:
						cur += a[i]
					else:
						cur += a[i] - 1
				elif a[i + 1] == 1:
					if a[i] % 2 == 0:
						cur += a[i] - 1
					else:
						cur += a[i]
			elif i == n - 1:
				cur += a[i]
	for _ in range(q):
		r = int(input())
		if n == 1 and a[0] == 1:
			print(r % (10 ** 9 + 7))
			continue
		if a[0] == 1 and r == 1:
			print(1)
			continue
		times = ceil(r / n) - 1
		lol = times * for_once
		b = r % n
		if b == 0:
			b = n
		if a[0] == 1:
			if r <= n:
				print(1)
			elif b == 1:
				print(lol % (10 ** 9 + 7))
			else:
				print((lol + 1) % (10 ** 9 + 7))
			continue
		print((lol + prefix[b - 1]) % (10 ** 9 + 7))


mod = 1000000007
t = int(input())
for k in range(0, t):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	if n == 1:
		q = int(input())
		for h in range(0, q):
			r = int(input())
			if a[0] % 2 == 1:
				print(a[0] % mod * (r % mod) % mod)
			else:
				print(((a[0] - 1) % mod * (r % mod) % mod + 1) % mod)
	else:
		ans = {}
		if a[0] != 1:
			for i in range(0, n):
				if i == 0:
					ans[i] = a[i]
				elif a[i - 1] % 2 != 1:
					ans[i] = (ans[i - 1] + a[i] % mod) % mod
				elif a[i - 1] != 1:
					ans[i] = (mod + ans[i - 1] - 1 + a[i] % mod) % mod
				else:
					ans[i] = (mod + ans[i - 2] - (a[i - 2] + 1) % 2 + a[i] % mod) % mod
			last = ans[n - 1]
			if a[n - 1] % 2 == 0:
				last = (mod + last - 1) % mod
		q = int(input())
		for h in range(0, q):
			r = int(input())
			if a[0] == 1:
				total = (int((r - 1) / n) % mod + 1) % mod
				if total != 1 and (r - 1) % n == 0:
					total = total - 1
				print(total)
			else:
				total = (int((r - 1) / n) % mod * last % mod + ans[(r - 1) % n]) % mod
				print(total)


import itertools
import math
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	q = int(input())
	rs = []
	for i in range(q):
		rs.append(int(input()))
	oneIndex = -1
	if arr[0] == 1:
		oneIndex = 0
	optimals = [0 for i in range(n)]
	optimals[0] = arr[0]
	for i in range(1, n):
		optimals[i] = optimals[i - 1]
		if arr[i] == 1:
			oneIndex = i
		if arr[i - 1] % 2 != 0 and arr[i - 1] != 1:
			optimals[i] -= 1
		if arr[i - 1] == 1 and i - 1 > 0 and (arr[i - 2] % 2 == 0):
			optimals[i] -= 2
		optimals[i] += arr[i]
	for i in range(q):
		r = rs[i]
		ans = 0
		if oneIndex != 0:
			ans += optimals[-1] * (r // n)
			if arr[-1] % 2 == 0 and r // n > 0:
				if r % n == 0:
					ans -= r // n - 1
				else:
					ans -= r // n
			if r % n != 0:
				ans += optimals[r % n - 1]
		else:
			ans += math.ceil(r / n)
			if r % n == 1 and r // n > 0:
				ans -= 1
		print(ans % mod)


import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_even(N):
	if N % 2 == 0:
		return N
	else:
		return N - 1

def get_odd(N):
	if N % 2 != 0:
		return N
	else:
		return N - 1
for _ in range(int(input())):
	N = int(input())
	K = pow(10, 9) + 7
	A = get_ints()
	Q = []
	for __ in range(int(input())):
		q = int(input())
		Q.append(q)
	q = max(Q) + 3
	dp = [0] * N
	ans = 0
	(chef, oppo) = (0, 0)
	chef_bul = True
	if N == 1 and A[0] == 1:
		for i in Q:
			print(i % K)
	elif A[0] == 1:
		for i in Q:
			if i == 1:
				ans = 1
			elif (i - 1) / N % 1 == 0:
				ans = i // N % K
			elif i / N % 1 == 0:
				ans = i // N % K
			else:
				ans = (i // N + 1) % K
			print(ans)
	else:
		for i in range(N):
			if A[(i + 1) % N] == 1:
				if A[i % N] == A[-1]:
					if chef_bul:
						ans = (ans + get_even(A[i % N])) % K
				elif A[i % N] == A[(N - 2) % N]:
					if chef_bul:
						ans = (ans + get_even(A[i % N])) % K
				elif chef_bul:
					ans = (ans + get_odd(A[i % N])) % K
					chef_bul = not chef_bul
			elif A[i % N] == A[-1]:
				if chef_bul == True:
					ans = (ans + get_odd(A[i % N])) % K
				chef_bul = not chef_bul
			elif A[i % N] == 1:
				if chef_bul == True:
					ans = (ans + 1) % K
				chef_bul = not chef_bul
			elif chef_bul == True:
				ans = (ans + get_even(A[i % N])) % K
			if A[i % N] == A[-1]:
				chef_bul = not chef_bul
			dp[i] = [ans, chef_bul]
		for q in Q:
			if q <= 3:
				ans = 0
				chef_bul = True
				for i in range(0, q):
					if i == q - 1:
						if chef_bul:
							ans = (ans + A[i % N]) % K
					elif A[(i + 1) % N] == 1:
						if A[i % N] == A[-1]:
							if i == q - 2:
								if chef_bul:
									ans = (ans + get_odd(A[i % N])) % K
								chef_bul = not chef_bul
							elif chef_bul:
								ans = (ans + get_even(A[i % N])) % K
						elif i == q - 2:
							if chef_bul:
								ans = (ans + get_even(A[i % N])) % K
						elif A[i % N] == A[(N - 2) % N]:
							if chef_bul:
								ans = (ans + get_even(A[i % N])) % K
						elif chef_bul:
							ans = (ans + get_odd(A[i % N])) % K
							chef_bul = not chef_bul
					elif A[i % N] == A[-1]:
						if chef_bul == True:
							ans = (ans + get_odd(A[i % N])) % K
						chef_bul = not chef_bul
					elif A[i % N] == 1:
						if chef_bul == True:
							ans = (ans + 1) % K
						chef_bul = not chef_bul
					elif chef_bul == True:
						ans = (ans + get_even(A[i % N])) % K
					if A[i % N] == A[-1]:
						chef_bul = not chef_bul
			else:
				ans = (dp[N - 1][0] * ((q - 3) // N) + dp[(q - 3) % N][0]) % K
				chef_bul = dp[(q - 3) % N][1]
				for i in range(q - 2, q):
					if i == q - 1:
						if chef_bul:
							ans = (ans + A[i % N]) % K
					elif A[(i + 1) % N] == 1:
						if A[i % N] == A[-1]:
							if i == q - 2:
								if chef_bul:
									ans = (ans + get_odd(A[i % N])) % K
								chef_bul = not chef_bul
							elif chef_bul:
								ans = (ans + get_even(A[i % N])) % K
						elif i == q - 2:
							if chef_bul:
								ans = (ans + get_even(A[i % N])) % K
						elif A[i % N] == A[(N - 2) % N]:
							if chef_bul:
								ans = (ans + get_even(A[i % N])) % K
						elif chef_bul:
							ans = (ans + get_odd(A[i % N])) % K
							chef_bul = not chef_bul
					elif A[i % N] == A[-1]:
						if chef_bul == True:
							ans = (ans + get_odd(A[i % N])) % K
						chef_bul = not chef_bul
					elif A[i % N] == 1:
						if chef_bul == True:
							ans = (ans + 1) % K
						chef_bul = not chef_bul
					elif chef_bul == True:
						ans = (ans + get_even(A[i % N])) % K
					if A[i % N] == A[-1]:
						chef_bul = not chef_bul
			print(ans)


def inp():
	return int(input())

def inl():
	return [int(i) for i in input().split()]
for _ in range(inp()):
	n = inp()
	a = inl()
	m = pow(10, 9) + 7
	flg = False
	t = -1
	for i in range(n):
		if a[i] == 1 and i == 0:
			flg = True
			break
		if a[i] == 1:
			t = i
			break
	if flg == True and n == 1:
		q = inp()
		for i in range(q):
			r = inp()
			print(r // n % m)
	elif flg == True:
		q = inp()
		for i in range(q):
			r = inp()
			if r % n == 1 and r >= n or r % n == 0:
				print(r // n % m)
			elif r % n == 1 and r == 1:
				print(1)
			else:
				print((r // n + 1) % m)
	elif t == -1 or t == n - 1:
		q = inp()
		dp = [0 for i in range(n + 1)]
		dp[1] = a[0]
		for i in range(2, n + 1):
			dp[i] = dp[i - 1] + a[i - 1]
			if a[i - 2] & 1 == 1:
				dp[i] = dp[i] - 1
		for i in range(q):
			r = inp()
			d = r // n
			rem = r % n
			ans = d * dp[n] + dp[rem]
			if d > 0:
				if a[n - 1] & 1 == 0:
					if rem == 0:
						ans = ans - (d - 1)
					else:
						ans = ans - d
			print(ans % m)
	else:
		q = inp()
		dp = [0 for i in range(n + 1)]
		dp[1] = a[0]
		for i in range(2, n + 1):
			dp[i] = dp[i - 1] + a[i - 1]
			if a[i - 2] == 1:
				if a[i - 3] & 1 == 0:
					dp[i] = dp[i] - 2
			elif a[i - 2] & 1 == 1:
				dp[i] = dp[i] - 1
		for i in range(q):
			r = inp()
			d = r // n
			rem = r % n
			ans = d * dp[n] + dp[rem]
			if d > 0:
				if a[n - 1] & 1 == 0:
					if rem == 0:
						ans = ans - (d - 1)
					else:
						ans = ans - d
			print(ans % m)


try:
	for t in range(int(input())):
		n = int(input())
		arr = [int(x) for x in input().split()][:n]
		temp = []
		s = 0
		if 1 in arr:
			if arr[0] != 1:
				for i in range(n):
					if arr[-1] == 1:
						s = s + arr[i]
						if arr[i] % 2 != 0 and i != n - 1:
							temp.append(s)
						elif arr[i] % 2 != 0 and i == n - 1:
							temp.append(s)
						else:
							temp.append(s)
						if arr[i] % 2 != 0:
							s = s - 1
					else:
						s = s + arr[i]
						temp.append(s)
						if arr[i] % 2 != 0 and arr[i] != 1:
							s = s - 1
						elif arr[i] == 1 and arr[i - 1] % 2 != 0:
							s = s
						elif arr[i] == 1 and arr[i - 1] % 2 == 0:
							s = s - 2
			for Q in range(int(input())):
				turn = int(input())
				if turn == 0:
					print('0')
				elif arr[0] != 1:
					if turn <= n:
						print(temp[turn - 1] % (10 ** 9 + 7))
					else:
						div = turn // n
						rem = turn % n
						answer = 0
						if rem == 0:
							if arr[-1] % 2 == 0:
								answer = temp[-1] * div - (div - 1)
							elif arr[-1] % 2 != 0:
								answer = temp[-1] * div
						elif arr[-1] % 2 == 0 and rem != 0:
							answer = temp[-1] * div - div + temp[rem - 1]
						else:
							answer = temp[-1] * div + temp[rem - 1]
						print(answer % (10 ** 9 + 7))
				elif len(arr) != 1:
					if turn == 0:
						print('0')
					elif turn <= len(arr):
						print('1')
					else:
						div = turn // n
						rem = turn % n
						if rem == 1 or rem == 0:
							answer = div
						else:
							answer = div + 1
						print(answer % (10 ** 9 + 7))
				else:
					answer = arr[0] * turn
					print(answer % (10 ** 9 + 7))
		else:
			for i in range(n):
				s = s + arr[i]
				temp.append(s)
				if arr[i] % 2 != 0:
					s = s - 1
			for Q in range(int(input())):
				turn = int(input())
				if turn == 0:
					print('0')
				elif turn <= n:
					print(temp[turn - 1] % (10 ** 9 + 7))
				else:
					div = turn // n
					rem = turn % n
					answer = 0
					if rem == 0:
						if arr[-1] % 2 == 0:
							answer = temp[-1] * div - (div - 1)
						elif arr[-1] % 2 != 0:
							answer = temp[-1] * div
					elif arr[-1] % 2 == 0 and rem != 0:
						answer = temp[-1] * div - div + temp[rem - 1]
					else:
						answer = temp[-1] * div + temp[rem - 1]
					print(answer % (10 ** 9 + 7))
except:
	pass


def get_sums(N, numbers):
	skip_flag = False
	final_sum = []
	cycle_sum = 0
	for i in range(N - 1):
		if skip_flag:
			skip_flag = False
			continue
		if numbers[i + 1] == 1 and i < N - 2:
			if numbers[i] % 2:
				cycle_sum += numbers[i]
				final_sum.extend([cycle_sum, cycle_sum])
			else:
				cycle_sum += numbers[i] - 1
				final_sum.extend([cycle_sum + 1, cycle_sum + 2])
			skip_flag = True
		else:
			final_sum.append(cycle_sum + numbers[i])
			cycle_sum += numbers[i] - numbers[i] % 2
	final_sum.append(cycle_sum + numbers[N - 1])
	cycle_sum += numbers[N - 1] - (numbers[N - 1] - 1) % 2
	return (final_sum, cycle_sum % 1000000007)
for _ in range(int(input())):
	N = int(input())
	numbers = tuple(map(int, input().split()))
	Q = int(input())
	if numbers[0] == 1:
		if N == 1:
			for j in range(Q):
				query = int(input())
				print(query % 1000000007)
		else:
			for j in range(Q):
				query = int(input())
				print((1 + max(query - 2, 0) // N) % 1000000007)
	else:
		(final_sum, cycle_sum) = get_sums(N, numbers)
		for j in range(Q):
			query = int(input())
			if not query % N:
				print(((query - 1) // N * cycle_sum + final_sum[N - 1]) % 1000000007)
			else:
				print((query // N * cycle_sum + final_sum[query % N - 1]) % 1000000007)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ps = []
	if a[0] % 2 != 0:
		ps.append(a[0] - 1)
	else:
		ps.append(a[0])
	s = 0
	for j in range(1, n):
		if a[j] % 2 != 0:
			ps.append(ps[j - 1] + a[j] - 1)
		elif a[j] % 2 == 0:
			ps.append(ps[j - 1] + a[j])
	f = 1
	if 1 in a:
		x = a.index(1)
	else:
		f = 0
	q = int(input())
	for j in range(0, q):
		r = int(input())
		if n == 1 and a[0] == 1:
			if r == 1:
				print(1)
			elif r % n == 1:
				print(1)
			elif r % n == 0:
				print(r // n % (10 ** 9 + 7))
			else:
				print((r / n + 1) % (10 ** 9 + 7))
		elif n == 1 and a[0] != 1:
			s = 0
			if a[0] % 2 == 0:
				s = (r - 1) * (a[0] - 1) + a[0]
			elif a[0] % 2 != 0:
				s = s + r * a[0]
			print(s % (10 ** 9 + 7))
		elif f == 0:
			if r <= n:
				s = 0
				if a[r - 1] % 2 == 0:
					print(ps[r - 1] % (10 ** 9 + 7))
				elif a[r - 1] % 2 != 0:
					print((ps[r - 1] + 1) % (10 ** 9 + 7))
			elif r % n == 0:
				s = 0
				p = r // n
				if a[n - 1] % 2 == 0:
					s = p * ps[n - 1] - 1 * (p - 1)
					print(s % (10 ** 9 + 7))
				elif a[n - 1] % 2 != 0:
					s = p * ps[n - 1] + 1 * p
					print(s % (10 ** 9 + 7))
			elif r % n != 0:
				p = r // n
				w = r % n - 1
				s = 0
				if a[n - 1] % 2 == 0:
					s = p * ps[n - 1] - 1 * p
					if a[w] % 2 == 0:
						s = s + ps[w]
					elif a[w] % 2 != 0:
						s = s + ps[w] + 1
					print(s % (10 ** 9 + 7))
				elif a[n - 1] % 2 != 0:
					s = p * ps[n - 1] + 1 * p
					if a[w] % 2 == 0:
						s = s + ps[w]
					elif a[w] % 2 != 0:
						s = s + ps[w] + 1
					print(s % (10 ** 9 + 7))
		elif a[0] == 1:
			s = 0
			if r <= n + 1:
				print(1 % (10 ** 9 + 7))
			elif r % n > 1:
				print((r // n + 1) % (10 ** 9 + 7))
			else:
				print(r // n % (10 ** 9 + 7))
		elif a[n - 1] == 1:
			s = 0
			if r <= n:
				if a[r - 1] % 2 != 0:
					s = s + ps[r - 1] + 1
				elif a[r - 1] % 2 == 0:
					s = s + ps[r - 1]
				print(s % (10 ** 9 + 7))
			elif r % n == 0:
				p = r // n
				s = s + ps[n - 1] * p + 1 * p
				print(s % (10 ** 9 + 7))
			elif r % n != 0:
				p = r // n
				s = s + ps[n - 1] * p + 1 * p
				w = r % n - 1
				if a[w] % 2 == 0:
					s = s + ps[w]
				elif a[w] % 2 != 0:
					s = s + ps[w] + 1
				print(s % (10 ** 9 + 7))
		else:
			s = 0
			if r - 1 < x:
				if a[r - 1] % 2 == 0:
					s = s + ps[r - 1]
				elif a[r - 1] % 2 != 0:
					s = s + ps[r - 1] + 1
				print(s % (10 ** 9 + 7))
			elif r <= n:
				s = s + ps[r - 1]
				if x == r - 1:
					if a[x - 1] % 2 != 0:
						s = s + 1
					elif a[x - 1] % 2 == 0:
						s = s + 1
				elif x != r - 1:
					if a[x - 1] % 2 != 0:
						s = s + 1
						if a[r - 1] % 2 != 0:
							s = s + 1
					elif a[x - 1] % 2 == 0:
						s = s - 1
						if a[r - 1] % 2 != 0:
							s = s + 1
				print(s % (10 ** 9 + 7))
			elif x != r % n - 1:
				p = r // n
				s = s + ps[n - 1] * p
				if r % n == 0:
					if a[n - 1] % 2 != 0:
						s = s + 1 * p
						if a[x - 1] % 2 == 0:
							s = s - 1 * p
						elif a[x - 1] % 2 != 0:
							s = s + 1 * p
					elif a[n - 1] % 2 == 0:
						s = s - 1 * (p - 1)
						if a[x - 1] % 2 == 0:
							s = s - 1 * p
						elif a[x - 1] % 2 != 0:
							s = s + 1 * p
					print(s % (10 ** 9 + 7))
				elif r % n != 0:
					w = r % n - 1
					s = s + ps[w]
					if a[n - 1] % 2 != 0:
						s = s + 1 * p
						if a[x - 1] % 2 == 0:
							s = s - 1 * p
							if w > x:
								s = s - 1
							if a[w] % 2 != 0:
								s = s + 1
						elif a[x - 1] % 2 != 0:
							s = s + 1 * p
							if w > x:
								s = s + 1
							if a[w] % 2 != 0:
								s = s + 1
					elif a[n - 1] % 2 == 0:
						s = s - 1 * p
						if a[x - 1] % 2 == 0:
							s = s - 1 * p
							if w > x:
								s = s - 1
							if a[w] % 2 != 0:
								s = s + 1
						elif a[x - 1] % 2 != 0:
							s = s + 1 * p
							if w > x:
								s = s + 1
							if a[w] % 2 != 0:
								s = s + 1
					print(s % (10 ** 9 + 7))
			else:
				s = 0
				p = r // n
				w = r % n - 1
				s = s + ps[n - 1] * p
				s = s + ps[w]
				if r % n != 0:
					if a[n - 1] % 2 != 0:
						s = s + 1 * p
						if a[x - 1] % 2 == 0:
							s = s - 1 * p
							s = s + 1
						elif a[x - 1] % 2 != 0:
							s = s + 1 * p
							s = s + 1
					elif a[n - 1] % 2 == 0:
						s = s - 1 * p
						if a[x - 1] % 2 == 0:
							s = s - 1 * p
							s = s + 1
						elif a[x - 1] % 2 != 0:
							s = s + 1 * p
							s = s + 1
				print(s % (10 ** 9 + 7))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	u = 10 ** 9 + 7
	q = int(input())
	if l[0] == 1:
		for i in range(q):
			m = int(input())
			s = 0
			if m % n <= 1:
				s = m // n % u
				if s == 0:
					s = 1
			else:
				s = (m // n + 1) % u
			print(s % 1000000007)
	else:
		dp = [0] * n
		dp[0] = l[0]
		for i in range(1, n):
			dp[i] = dp[i - 1] + l[i]
			if l[i - 1] % 2 != 0 and l[i - 1] > 1:
				dp[i] -= 1
			elif l[i - 1] == 1:
				if l[i - 2] % 2 == 0:
					dp[i] -= 2
		for i in range(q):
			m = int(input())
			s = 0
			if m <= n:
				s = dp[m - 1] % u
			elif m % n == 0:
				s = dp[-1] % u * (m // n % u) % u
				if l[-1] % 2 == 0:
					s -= m // n - 1
			else:
				s = dp[-1] % u * (m // n % u) % u
				if l[-1] % 2 == 0:
					s -= m // n
				s = (s + dp[m % n - 1] % u) % u
			print(s % 1000000007)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	q = int(input())
	pt = 1
	if pt == 1:
		ck = 1
		cf = 0
		p = 1
		if p == 1:
			r = 5 * n
			for j in range(r):
				v = j % n
				if v == 0 and j != 0:
					break
				if j == r - 1:
					if ck == 1:
						cf += l[v]
				elif v == n - 1:
					if l[v] == 1:
						if ck == 1:
							cf += l[v]
						if ck == 1:
							ck = 0
						else:
							ck = 1
					elif l[0] == 1:
						if l[v] % 2 == 0:
							if j + 1 == r - 1:
								if ck == 1:
									cf += l[v] - 1
								if ck == 1:
									ck = 0
								else:
									ck = 1
							elif ck == 1:
								cf += l[v]
						elif j + 1 == r - 1:
							if ck == 1:
								cf += l[v]
							if ck == 1:
								ck = 0
							else:
								ck = 1
						elif ck == 1:
							cf += l[v] - 1
					elif l[v] % 2 == 0:
						if ck == 1:
							cf += l[v] - 1
						if ck == 1:
							ck = 0
						else:
							ck = 1
					else:
						if ck == 1:
							cf += l[v]
						if ck == 1:
							ck = 0
						else:
							ck = 1
				elif l[v] == 1:
					if ck == 1:
						cf += l[v]
						ck = 0
					else:
						ck = 1
				elif l[v] % 2 == 0:
					if l[v + 1] == 1:
						if j + 1 == r - 1:
							if ck == 1:
								cf += l[v]
						elif (j + 2) % n == 0:
							if ck == 1:
								cf += l[v]
						else:
							if ck == 1:
								cf += l[v] - 1
							if ck == 1:
								ck = 0
							else:
								ck = 1
					elif ck == 1:
						cf += l[v]
				elif l[v + 1] == 1:
					if j + 1 == r - 1:
						if ck == 1:
							cf += l[v]
						if ck == 1:
							ck = 0
						else:
							ck = 1
					elif (j + 2) % n == 0:
						if ck == 1:
							cf += l[v] - 1
					else:
						if ck == 1:
							cf += l[v]
						if ck == 1:
							ck = 0
						else:
							ck = 1
				elif ck == 1:
					cf += l[v] - 1
	c1 = 1
	cval = 0
	cf1 = [0] * n
	for j in range(n):
		if l[j] == 1:
			if j == 0:
				cf1[j] = 1
				if c1 == 1:
					c1 = 0
				else:
					c1 = 1
				cval += 1
			else:
				if c1 == 1:
					cf1[j] = cval + l[j]
					cval += 1
					c1 = 0
				else:
					cf1[j] = cval
					c1 = 1
				if l[j - 1] % 2 == 0:
					cval -= 2
					if c1 == 1:
						c1 = 0
					else:
						c1 = 1
				elif c1 == 1:
					c1 = 0
				else:
					c1 = 1
		elif l[j] % 2 == 0:
			if c1 == 1:
				cf1[j] = cval + l[j]
				cval += l[j]
			else:
				cf1[j] = cval
		elif c1 == 1:
			cf1[j] = cval + l[j]
			cval += l[j] - 1
		else:
			cf1[j] = cval
	for i in range(q):
		r = int(input())
		qu = r // n
		rem = r % n
		if rem == 0:
			qu = qu - 1
			rem = n
		ans = qu * cf + cf1[rem - 1]
		if qu >= 1 and rem == 1 and (l[0] == 1) and (n >= 2):
			ans -= 1
		print(ans % (10 ** 9 + 7))


import sys, collections, math

def in_out():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = int(input())
	mod = 10 ** 9 + 7
	a = list(map(int, input().split()))
	a = [0] + a
	q = int(input())
	val1 = [0] * (n + 1)
	val2 = [0] * (n + 1)
	if a[1] == 1:
		for i in range(1, n + 1):
			val1[i] = 1
	elif a[n] == 1:
		if a[1] % 2 == 0:
			val1[1] = a[1]
		else:
			val1[1] = a[1] - 1
		for i in range(2, n):
			if a[i] % 2 == 0:
				val = a[i]
			else:
				val = a[i] - 1
			val1[i] = (val1[i - 1] + val) % mod
		val1[n] = (val1[n - 1] + 1) % mod
	else:
		ans = 0
		for i in range(1, n + 1):
			nextVal = -1
			if i < n:
				nextVal = a[i + 1]
			if nextVal == 1:
				if a[i] % 2 == 0:
					curr = a[i] - 1
				else:
					curr = a[i]
			elif i == n:
				if a[i] % 2 == 0:
					curr = a[i] - 1
				else:
					curr = a[i]
			elif a[i] % 2 == 0:
				curr = a[i]
			else:
				curr = a[i] - 1
			ans += curr
			ans %= mod
			val1[i] = ans
	if a[1] == 1:
		val2[1] = 0
		for i in range(2, n + 1):
			val2[i] = 1
	elif a[n] == 1:
		val2[1] = a[1]
		for i in range(2, n + 1):
			val2[i] = (val1[i - 1] + a[i]) % mod
	else:
		val2[1] = a[1]
		for i in range(2, n + 1):
			if a[i] == 1:
				if a[i - 1] % 2 == 0:
					val2[i] = (val1[i - 1] + a[i] + 1) % mod
				else:
					val2[i] = val1[i - 1]
			else:
				val2[i] = (val1[i - 1] + a[i]) % mod
	for i in range(q):
		r = int(input())
		ans = 0
		times = r // n
		rem = r % n
		if rem > 0:
			ans = times * val1[n] % mod
			ans += val2[rem]
		elif rem == 0:
			ans = (times - 1) * val1[n] % mod
			ans += val2[n]
		if a[1] == 1 and r == 1:
			ans = 1
		elif n == 1 and a[1] == 1:
			ans = r
		ans %= mod
		print(ans)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	l = []
	for p in range(2, n + 1):
		if prime[p]:
			l += [p]
	return l

def i1():
	return int(input())

def i2():
	return map(int, input().split())

def i3():
	return list(map(int, input().split()))

def i4():
	return input()
m = 10 ** 9 + 7
for _ in range(i1()):
	n = i1()
	a = i3()
	x = 0
	y = -1
	l = [0 for i in range(100000)]
	for i in range(n - 1):
		if a[i] == 1:
			if i == 0:
				x = 1
			else:
				x = 2
				y = i
	if x == 1:
		for i in range(i1()):
			r = i1()
			if r % n == 0:
				print(r // n % m)
			elif r % n == 1 and r > n:
				print(r // n % m)
			else:
				print((r // n + 1) % m)
	elif x == 2:
		s = 0
		for i in range(n - 1):
			if i == y - 1:
				if a[i] % 2 == 0:
					s = s + a[i] - 1
				else:
					s += a[i]
			elif a[i] % 2 == 0:
				s += a[i]
			else:
				s += a[i] - 1
			l[i] = s
		if a[n - 1] % 2 == 0:
			s += a[n - 1] - 1
		else:
			s += a[n - 1]
		for i in range(i1()):
			r = i1()
			if r % n == 0:
				if a[n - 1] % 2 == 0:
					print((r // n * s + 1) % m)
				else:
					print(r // n * s % m)
			elif y == r % n - 1:
				if a[y - 1] % 2 == 0:
					print((r // n * s + 2 + l[r % n - 1]) % m)
				else:
					print((r // n * s + l[r % n - 1]) % m)
			elif y - 1 == r % n - 1:
				if a[y - 1] % 2 == 0:
					print((r // n * s + l[r % n - 1] + 1) % m)
				else:
					print((r // n * s + l[r % n - 1]) % m)
			elif a[r % n - 1] % 2 != 0:
				print((r // n * s + l[r % n - 1] + 1) % m)
			else:
				print((r // n * s + l[r % n - 1]) % m)
	else:
		s = 0
		for i in range(n - 1):
			if a[i] % 2 == 0:
				s += a[i]
			else:
				s += a[i] - 1
			l[i] = s
		if a[n - 1] % 2 == 0:
			s += a[n - 1] - 1
		else:
			s += a[n - 1]
		for i in range(i1()):
			r = i1()
			if r % n == 0:
				if a[n - 1] % 2 == 0:
					print((r // n * s + 1) % m)
				else:
					print(r // n * s % m)
			elif a[r % n - 1] % 2 != 0:
				print((r // n * s + l[r % n - 1] + 1) % m)
			else:
				print((r // n * s + l[r % n - 1]) % m)


def noOne(arr):
	n = len(arr)
	evenSum = [0] * n
	curEvenSum = 0
	for i in range(n - 1):
		if arr[i] % 2 == 0:
			curEvenSum += arr[i]
		else:
			curEvenSum += arr[i] - 1
		evenSum[i] = curEvenSum
	if arr[-1] % 2 == 0:
		curEvenSum += arr[-1] - 1
	else:
		curEvenSum += arr[-1]
	q = int(stdin.readline())
	for i in range(q):
		r = int(stdin.readline())
		mult = r // n
		if r % n == 0:
			if arr[-1] % 2 == 0:
				answer = (mult * curEvenSum + 1) % mod
			else:
				answer = mult * curEvenSum % mod
		else:
			rem = r % n
			if arr[rem - 1] % 2 == 0:
				answer = (mult * curEvenSum + evenSum[rem - 1]) % mod
			else:
				answer = (mult * curEvenSum + evenSum[rem - 1] + 1) % mod
		answer = int(answer % mod)
		stdout.write(str(answer) + '\n')

def oneBeg(arr):
	n = len(arr)
	q = int(stdin.readline())
	for i in range(q):
		r = int(stdin.readline())
		if r % n == 0:
			stdout.write(str(int(r // n % mod)) + '\n')
		else:
			if r % n == 1 and r > n:
				answer = r // n % mod
			else:
				answer = (r // n + 1) % mod
			answer = int(answer % mod)
			stdout.write(str(answer) + '\n')

def oneEnd(arr):
	noOne(arr)

def oneMid(arr, ind1):
	n = len(arr)
	evenSum = [0] * n
	curEvenTotal = 0
	for i in range(n - 1):
		if i == ind1 - 1:
			if arr[i] % 2 == 0:
				curEvenTotal += arr[i] - 1
			else:
				curEvenTotal += arr[i]
		elif arr[i] % 2 == 0:
			curEvenTotal += arr[i]
		else:
			curEvenTotal += arr[i] - 1
		evenSum[i] = curEvenTotal
	if arr[-1] % 2 == 0:
		curEvenTotal += arr[-1] - 1
	else:
		curEvenTotal += arr[-1]
	q = int(stdin.readline())
	for i in range(q):
		r = int(stdin.readline())
		mult = r // n
		if r % n == 0:
			if arr[-1] % 2 == 0:
				answer = (curEvenTotal * mult + 1) % mod
			else:
				answer = curEvenTotal * mult % mod
		else:
			rem = r % n
			if rem == ind1 + 1:
				if arr[ind1 - 1] % 2 == 0:
					answer = (mult * curEvenTotal + evenSum[rem - 1] + 2) % mod
				else:
					answer = (mult * curEvenTotal + evenSum[rem - 1]) % mod
			elif rem == ind1:
				if arr[ind1 - 1] % 2 == 0:
					answer = (mult * curEvenTotal + evenSum[rem - 1] + 1) % mod
				else:
					answer = (mult * curEvenTotal + evenSum[rem - 1]) % mod
			elif arr[rem - 1] % 2 == 0:
				answer = (mult * curEvenTotal + evenSum[rem - 1]) % mod
			else:
				answer = (mult * curEvenTotal + evenSum[rem - 1] + 1) % mod
		answer = int(answer % mod)
		stdout.write(str(answer) + '\n')

def callFunction(ind, arr):
	n = len(arr)
	if ind == 0:
		oneBeg(arr)
	elif ind == n - 1:
		oneEnd(arr)
	elif ind == -1:
		noOne(arr)
	else:
		oneMid(arr, ind)

def notOne(num):
	q = int(stdin.readline())
	for i in range(q):
		r = int(stdin.readline())
		if num % 2 == 0:
			answer = (num - 1) % mod * (r % mod) % mod
			if r > 1:
				answer += 1
		else:
			answer = num % mod * (r % mod) % mod
		answer = answer % mod
		answer = int(answer)
		stdout.write(str(answer) + '\n')

def onlyOne(arr):
	q = int(stdin.readline())
	for i in range(q):
		r = int(stdin.readline())
		r = int(r % mod)
		stdout.write(str(r) + '\n')

def main():
	t = int(stdin.readline())
	for i in range(t):
		n = int(stdin.readline())
		arr = [0] * n
		inx = 0
		ind1 = -1
		for x in stdin.readline().split():
			arr[inx] = int(x)
			if int(x) == 1:
				ind1 = inx
			inx += 1
		if n == 1:
			if arr[0] != 1:
				noOne(arr)
			else:
				onlyOne(arr)
		else:
			callFunction(ind1, arr)
from sys import stdin, stdout
mod = 1000000007
main()


M = 1000000007
for t in range(int(input())):
	s = 0
	sa = []
	ioo = -1
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(len(a)):
		if a[i] == 1:
			ioo = i
		if a[i] % 2 != 0:
			s = (s + (a[i] - 1)) % M
		else:
			s = (s + a[i]) % M
		sa.append(s)
	q = int(input())
	for te in range(q):
		r = int(input())
		if ioo >= 0:
			if ioo == 0:
				if r <= n:
					ans = 1
				else:
					noi = r // n
					d = r % n
					if d > 1:
						ans = (noi + 1) % M
					else:
						ans = noi % M
			elif ioo == n - 1:
				if r < n:
					if a[r - 1] % 2 == 0:
						ans = sa[r - 1]
					else:
						ans = sa[r - 1] + 1
				if r == n:
					ans = sa[r - 1] + 1
				if r > n:
					noi = r // n
					d = r % n
					ans = (sa[n - 1] + 1) * noi % M
					if d > 0:
						if a[d - 1] % 2 == 0:
							ans = (ans + sa[d - 1]) % M
						else:
							ans = (ans + sa[d - 1] + 1) % M
			elif r <= n:
				if r - 1 <= ioo:
					if a[r - 1] % 2 == 0:
						ans = sa[r - 1]
					else:
						ans = sa[r - 1] + 1
				if r - 1 > ioo:
					if a[ioo - 1] % 2 == 0:
						adt = sa[ioo - 1] - 1
					else:
						adt = sa[ioo - 1] + 1
					if a[r - 1] % 2 == 0:
						fdt = sa[r - 1] - sa[ioo]
					else:
						fdt = sa[r - 1] - sa[ioo] + 1
					ans = (adt + fdt) % M
			else:
				noi = r // n
				d = r % n
				if a[ioo - 1] % 2 == 0:
					adt = sa[ioo - 1] - 1
				else:
					adt = sa[ioo - 1] + 1
				if a[n - 1] % 2 == 0:
					fdt = sa[n - 1] - sa[ioo] - 1
				else:
					fdt = sa[n - 1] - sa[ioo] + 1
				adt = (adt + fdt) % M
				ans = adt * noi % M
				if d == 0:
					if a[n - 1] % 2 == 0:
						ans = ans + 1
				if d > 0:
					if d - 1 <= ioo:
						if a[d - 1] % 2 == 0:
							ans = (ans + sa[d - 1]) % M
						else:
							ans = (ans + sa[d - 1] + 1) % M
					else:
						if a[ioo - 1] % 2 == 0:
							sdt = sa[ioo] - 1
						else:
							sdt = sa[ioo] + 1
						if a[d - 1] % 2 == 0:
							ddt = sa[d - 1] - sa[ioo]
						else:
							ddt = sa[d - 1] - sa[ioo] + 1
						ans = (ans + sdt) % M
						ans = (ans + ddt) % M
		else:
			if r <= n:
				if a[r - 1] % 2 == 0:
					ans = sa[r - 1]
				else:
					ans = sa[r - 1] + 1
			if r > n:
				noi = r // n
				d = r % n
				if a[n - 1] % 2 == 0:
					adt = sa[n - 1] - 1
				else:
					adt = sa[n - 1] + 1
				ans = adt * noi % M
				if d == 0:
					if a[n - 1] % 2 == 0:
						ans = ans + 1
				if d > 0:
					if a[d - 1] % 2 == 0:
						ans = (ans + sa[d - 1]) % M
					else:
						ans = (ans + sa[d - 1] + 1) % M
		print(ans)


def nearest_lower_even_number(number):
	return number >> 1 << 1

def nearest_lower_odd_number(number):
	return (number - (number >> 1) << 1) - 1

def payout_if_one_is_last_or_absent(sequence):
	payout = [nearest_lower_even_number(sequence[0])]
	for s in sequence[1:-1]:
		payout.append(payout[-1] + nearest_lower_even_number(s))
	payout.append(payout[-1] + nearest_lower_odd_number(sequence[-1]))
	return payout

def result_if_one_is_first(length, number_of_turns):
	(quotient, remainder) = divmod(number_of_turns, length)
	if number_of_turns == 1:
		result = 1
	elif remainder <= 1:
		result = quotient
	else:
		result = quotient + 1
	return result

def result_if_one_is_absent(payout, sequence, length, number_of_turns):
	(quotient, remainder) = divmod(number_of_turns, length)
	result = quotient * payout[-1]
	if remainder == 0:
		result += -payout[-1] + payout[-2] + sequence[-1]
	elif remainder == 1:
		result += sequence[0]
	else:
		result += payout[remainder - 2] + sequence[remainder - 1]
	return result

def result_if_one_is_last(payout, sequence, length, number_of_turns):
	(quotient, remainder) = divmod(number_of_turns, length)
	result = quotient * payout[-1]
	if remainder > 0:
		result += sequence[remainder - 1]
	if remainder > 1:
		result += payout[remainder - 2]
	return result

def result_if_one_is_inside(payout, sequence, length, index_of_one, number_of_turns):
	(quotient, remainder) = divmod(number_of_turns, length)
	result = quotient * payout[-1]
	if remainder == 0:
		result += -payout[-1] + payout[-2] + sequence[-1]
	elif remainder == 1:
		result += sequence[0]
	elif remainder == index_of_one + 1:
		if remainder >= 3:
			result += payout[remainder - 3] + nearest_lower_even_number(sequence[remainder - 2]) + 1
		else:
			result += nearest_lower_even_number(sequence[0]) + 1
	else:
		result += payout[remainder - 2] + sequence[remainder - 1]
	return result
for _ in range(int(input())):
	(length, sequence, queries) = (int(input()), [int(x) for x in input().split()], [int(input()) for _ in range(int(input()))])
	if length == 1:
		if sequence[0] & 1 == 1:
			result = lambda q: sequence[0] * q
		else:
			result = lambda q: (sequence[0] - 1) * q + 1
	elif sequence[0] == 1:
		result = lambda q: result_if_one_is_first(length, q)
	elif sequence[-1] == 1:
		payout = payout_if_one_is_last_or_absent(sequence)
		result = lambda q: result_if_one_is_last(payout, sequence, length, q)
	else:
		try:
			index_of_one = sequence.index(1)
			payout = []
			for (i, s) in enumerate(sequence):
				if i == 0:
					if index_of_one == 1:
						payout.append(nearest_lower_odd_number(s))
					else:
						payout.append(nearest_lower_even_number(s))
				elif i == index_of_one - 1 or i == length - 1:
					payout.append(payout[-1] + nearest_lower_odd_number(s))
				elif i == index_of_one:
					payout.append(payout[-1])
				else:
					payout.append(payout[-1] + nearest_lower_even_number(s))
			result = lambda q: result_if_one_is_inside(payout, sequence, length, index_of_one, q)
		except ValueError:
			payout = payout_if_one_is_last_or_absent(sequence)
			result = lambda q: result_if_one_is_absent(payout, sequence, length, q)
	print('\n'.join((str(result(q) % 1000000007) for q in queries)))


import math
mod = 1000000000.0 + 7
T = int(input())
for _ in range(T):
	N = int(input())
	lst = [int(x) for x in input().split(' ')]
	lst = [0] + lst
	wins = [0] * (N + 1)
	evenends = 0
	wins[1] = lst[1]
	if lst[1] != 1:
		for i in range(2, N + 1):
			if lst[i - 1] % 2 != 0:
				if lst[i - 1] != 1:
					wins[i] = (wins[i - 1] % mod - 1 % mod + lst[i] % mod) % mod
				elif lst[i - 1] == 1:
					if lst[i - 2] % 2 != 0:
						wins[i] = (wins[i - 2] % mod + lst[i] % mod) % mod
					else:
						wins[i] = (wins[i - 2] % mod - 1 + lst[i] % mod) % mod
			elif lst[i - 1] % 2 == 0:
				wins[i] = (wins[i - 1] % mod + lst[i] % mod) % mod
		if lst[N] % 2 == 0:
			evenends += 1
	Q = int(input())
	for j in range(Q):
		R = int(input())
		nwin = 0
		if lst[1] == 1:
			if R % N == 1 and R != 1:
				nwin = (math.ceil(R / N) % mod - 1) % mod
			else:
				nwin = math.ceil(R / N) % mod % mod
			print(int(nwin % mod))
		else:
			qrn = int(R // N)
			rrn = int(R % N)
			if evenends != 1:
				temp = qrn % mod * wins[N] % mod
				nwin = (temp % mod + wins[rrn]) % mod
			else:
				t = qrn
				if rrn == 0:
					t -= 1
				nwin = (wins[N] % mod - 1) * t % mod
				if rrn == 0:
					rrn = N
				nwin = (nwin % mod + wins[rrn] % mod) % mod
			print(int(nwin % mod))


import math
T = int(input())
for q in range(T):
	N = int(input())
	K = list(map(int, input().split()))
	whichis1 = 0
	while whichis1 < N and 1 != K[whichis1]:
		whichis1 += 1
	if N == whichis1:
		whichis1 = -1
	Total = 0
	Remainder = [0] * N
	if N > 1 and 0 != whichis1:
		warn1 = 1 if whichis1 < N - 1 and whichis1 > -1 else 0
		for i in range(N):
			Remainder[i] = Total + K[i]
			if i == N - 1 or (warn1 and i + 1 == whichis1):
				Total = Total + K[i] - (K[i] + 1) % 2
			else:
				Total = Total + K[i] - K[i] % 2
		if warn1 and K[whichis1 - 1] % 2 != 0:
			Remainder[whichis1] -= 1
		if warn1 and K[whichis1 - 1] % 2 == 0:
			Remainder[whichis1] += 1
	Q = int(input())
	for i in range(Q):
		R = int(input())
		if 1 == N:
			print(((R - 1) * (K[0] - (K[0] + 1) % 2) + K[0]) % 1000000007)
		elif 0 == whichis1:
			print((1 if 1 == R else math.ceil((R - 1) / N)) % 1000000007)
		else:
			print((math.floor((R - 1) / N) * Total + Remainder[(R - 1) % N]) % 1000000007)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	mod = 10 ** 9 + 7
	if 1 in a and a.index(1) != n - 1:
		if a[0] == 1:
			t = int(input())
			for j in range(t):
				q = int(input())
				if q % n == 0:
					print(q // n % mod)
				elif q % n == 1 and q > n:
					print(q // n % mod)
				else:
					print((q // n + 1) % mod)
		else:
			ind = a.index(1)
			temp = [0] * n
			s = 0
			for i in range(n - 1):
				if i != ind - 1:
					if a[i] % 2 == 1:
						s += a[i] - 1
						temp[i] = s
					else:
						s += a[i]
						temp[i] = s
				elif a[i] % 2 == 0:
					s += a[i] - 1
					temp[i] = s
				else:
					s += a[i]
					temp[i] = s
			if a[n - 1] % 2 == 0:
				s += a[n - 1] - 1
			else:
				s += a[n - 1]
			s = s % mod
			t = int(input())
			for j in range(t):
				q = int(input())
				if q % n == 0:
					if a[n - 1] % 2 == 0:
						print((q // n * s + 1) % mod)
					else:
						print(q // n * s % mod)
				elif ind == q % n - 1:
					if a[q % n - 2] % 2 == 0:
						print((q // n * s % mod + (temp[q % n - 1] + 2)) % mod)
					else:
						print((q // n * s % mod + temp[q % n - 1]) % mod)
				elif ind - 1 == q % n - 1:
					if a[q % n - 1] % 2 == 0:
						print((q // n * s % mod + (temp[q % n - 1] + 1)) % mod)
					else:
						print((q // n * s % mod + temp[q % n - 1]) % mod)
				elif a[q % n - 1] % 2 == 1:
					print((q // n * s % mod + (temp[q % n - 1] + 1)) % mod)
				else:
					print((q // n * s % mod + temp[q % n - 1]) % mod)
	else:
		temp = [0] * n
		s = 0
		for i in range(n - 1):
			if a[i] % 2 == 1:
				s += a[i] - 1
				temp[i] = s
			else:
				s += a[i]
				temp[i] = s
		if a[n - 1] % 2 == 0:
			s += a[n - 1] - 1
		else:
			s += a[n - 1]
		s = s % mod
		t = int(input())
		for j in range(t):
			q = int(input())
			if q % n == 0:
				if a[n - 1] % 2 == 0:
					print((q // n * s + 1) % mod)
				else:
					print(q // n * s % mod)
			elif a[q % n - 1] % 2 == 1:
				print((q // n * s % mod + (temp[q % n - 1] + 1)) % mod)
			else:
				print((q // n * s % mod + temp[q % n - 1]) % mod)


m = 1000000007
T = int(input())
while T:
	N = int(input())
	A = list(map(int, input().split()))
	onePos = -1
	if A[0] == 1:
		Q = int(input())
		while Q:
			R = int(input())
			if R % N == 0:
				print(int(R / N) % m)
			elif R % N == 1 and R > N:
				print(int(R / N) % m)
			else:
				print((int(R / N) + 1) % m)
			Q -= 1
	else:
		arr = list()
		chef = 0
		for i in range(N - 1):
			if A[i + 1] == 1 and i + 1 != N - 1:
				onePos = i + 1
				if not A[i] & 1:
					chef += A[i] - 1
					arr.append(chef)
				else:
					chef += A[i]
					arr.append(chef)
			elif not A[i] & 1:
				chef += A[i]
				arr.append(chef)
			else:
				chef += A[i] - 1
				arr.append(chef)
		if A[N - 1] % 2 == 0:
			chef += A[N - 1] - 1
		else:
			chef += A[N - 1]
		Q = int(input())
		while Q:
			R = int(input())
			if R % N == 0:
				if not A[N - 1] & 1:
					print((int(R / N) * chef + 1) % m)
				else:
					print(int(R / N) * chef % m)
			elif onePos == R % N - 1:
				if not A[onePos - 1] & 1:
					print((int(R / N) * chef + 2 + arr[R % N - 1]) % m)
				else:
					print((int(R / N) * chef + arr[R % N - 1]) % m)
			elif onePos - 1 == R % N - 1:
				if not A[onePos - 1] & 1:
					print((int(R / N) * chef + arr[R % N - 1] + 1) % m)
				else:
					print((int(R / N) * chef + arr[R % N - 1]) % m)
			elif A[R % N - 1] % 2 != 0:
				print((int(R / N) * chef + arr[R % N - 1] + 1) % m)
			else:
				print((int(R / N) * chef + arr[R % N - 1]) % m)
			Q -= 1
	T -= 1


from sys import stdin
input = stdin.readline

def func1(l, qq, modulus):
	if l[0] % 2 == 0:
		for rr in qq:
			print(((rr - 1) * (l[0] - 1) + l[0]) % modulus)
	else:
		for rr in qq:
			print(rr * l[0] % modulus)
	return

def func2(nn, l, qq, modulus):
	mm = [None] * nn
	res = 0
	for i in range(nn):
		mm[i] = res + l[i]
		if i != nn - 1:
			if l[i] % 2 == 0:
				res = res + l[i]
			else:
				res = res + l[i] - 1
		elif l[i] % 2 == 0:
			res = res + l[i] - 1
		else:
			res = res + l[i]
	for rr in qq:
		QQ = (rr - 1) // nn
		RR = (rr - 1) % nn
		print((res * QQ + mm[RR]) % modulus)
	return

def func3(nn, qq, modulus):
	for rr in qq:
		if rr == 1:
			print(1)
			continue
		if (rr - 1) % nn == 0:
			print((rr - 1) // nn % modulus)
		else:
			print(((rr - 1) // nn + 1) % modulus)
	return

def func4(nn, l, qq, modulus):
	mm = [None] * nn
	res = 0
	for i in range(nn):
		mm[i] = res + l[i]
		if i != nn - 1:
			if l[i] % 2 == 0:
				res = res + l[i]
			else:
				res = res + l[i] - 1
		elif l[i] % 2 == 0:
			res = res + l[i] - 1
		else:
			res = res + l[i]
	for rr in qq:
		QQ = (rr - 1) // nn
		RR = (rr - 1) % nn
		print((res * QQ + mm[RR]) % modulus)
	return

def solve2(nn, l, qq):
	modulus = 10 ** 9 + 7
	if nn == 1:
		func1(l, qq, modulus)
		return
	if 1 not in l:
		func2(nn, l, qq, modulus)
		return
	if l[0] == 1:
		func3(nn, qq, modulus)
		return
	if l[nn - 1] == 1:
		func4(nn, l, qq, modulus)
		return
	res = 0
	xx = l.index(1)
	mm = [None] * nn
	i = 0
	while i <= xx - 2:
		mm[i] = res + l[i]
		if l[i] % 2 == 1:
			res = res + l[i] - 1
		else:
			res = res + l[i]
		i = i + 1
	mm[i] = res + l[i]
	if l[i] % 2 == 0:
		res = res + l[i] - 1
	else:
		res = res + l[i]
	i = i + 1
	if l[i - 1] % 2 == 1:
		mm[i] = mm[i - 1]
	else:
		mm[i] = mm[i - 1] + 1
	i = i + 1
	if i != nn - 1:
		mm[i] = res + l[i]
		if l[i] % 2 == 1:
			res = res + l[i] - 1
		else:
			res = res + l[i]
		i = i + 1
	else:
		mm[i] = res + l[i]
		if l[i] % 2 == 0:
			res = res + l[i] - 1
		else:
			res = res + l[i]
		i = i + 1
	while i < nn:
		mm[i] = res + l[i]
		if i == nn - 1:
			if l[i] % 2 == 1:
				res = res + l[i]
			else:
				res = res + l[i] - 1
			i = i + 1
			continue
		if l[i] % 2 == 1:
			res = res + l[i] - 1
		else:
			res = res + l[i]
		i = i + 1
	for rr in qq:
		QQ = (rr - 1) // nn
		RR = (rr - 1) % nn
		print((res * QQ + mm[RR]) % modulus)
	return

def solve1():
	nn = input()
	nn = int(nn)
	l = list(map(int, input().split()))
	queries = input()
	queries = int(queries)
	qq = []
	for xx in range(queries):
		qq.append(int(input()))
	solve2(nn, l, qq)

def solve():
	test_cases = input()
	test_cases = int(test_cases)
	for t in range(test_cases):
		solve1()
solve()


mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	one = -1
	pref = [0] * n
	for i in range(n):
		if a[i] == 1:
			one = i
		if i > 0:
			pref[i] = pref[i - 1]
		if i < n - 1:
			pref[i] += a[i] - a[i] % 2
		else:
			pref[i] += a[i] - (a[i] + 1) % 2
		pref[i] %= mod
	for iterator in range(q):
		turns = int(input())
		rem = turns % n
		q = int(turns / n % mod)
		ans = 0
		if one == 0:
			ans = q + (rem > 1 or q == 0)
			ans %= mod
		elif one == n - 1:
			ans = pref[n - 1] * q
			ans %= mod
			if rem:
				ans += pref[rem - 1]
				if a[rem - 1] & 1:
					ans += 1
			elif a[n - 1] % 2 == 0:
				ans += 1
			ans %= mod
		elif one >= 0:
			ans = (pref[n - 1] + (1 if a[one - 1] % 2 == 1 else -1)) * q
			ans %= mod
			if rem:
				if rem - 1 <= one:
					ans += pref[rem - 1]
				else:
					ans += pref[rem - 1] + (1 if a[one - 1] % 2 == 1 else -1)
				if a[rem - 1] & 1:
					ans += 1
			elif a[n - 1] % 2 == 0:
				ans += 1
			ans %= mod
		else:
			ans = pref[n - 1] * q
			ans %= mod
			if rem:
				ans += pref[rem - 1]
				if a[rem - 1] & 1:
					ans += 1
			elif a[n - 1] % 2 == 0:
				ans += 1
			ans %= mod
		print(ans)


from sys import stdin, stdout, stderr, maxsize
tup = lambda : map(int, stdin.readline().split())
I = lambda : int(stdin.readline())
lint = lambda : [int(x) for x in stdin.readline().split()]
S = lambda : stdin.readline().replace('\n', '').strip()
stpr = lambda x: stdout.write(f'{x}' + '\n')
star = lambda x: print(' '.join(map(str, x)))
from math import ceil, floor
from _collections import defaultdict
from bisect import bisect_left, bisect_right
for _ in range(I()):
	n = I()
	ls = lint()
	s = 0
	st = []
	if 1 in ls:
		s = 1
	if ls[n - 1] == 1 or (ls[n - 1] % 2 and s == 0):
		(pre, p) = ([0] * n, 0)
		for i in range(n):
			if ls[i] % 2 != 0 and i != n - 1:
				p = p + ls[i] - 1
			else:
				p = p + ls[i]
			pre[i] = p
		for _ in range(I()):
			a = I()
			d = a // n * pre[n - 1]
			if a % n == 0:
				st.append(d % 1000000007)
			elif ls[a % n - 1] % 2 != 0:
				st.append((d + pre[a % n - 1] + 1) % 1000000007)
			else:
				st.append((d + pre[a % n - 1]) % 1000000007)
	elif ls[0] == 1:
		for _ in range(I()):
			b = I()
			if b <= n + 1:
				st.append(1)
			elif b % n == 1 or b % n == 0:
				st.append(b // n % 1000000007)
			else:
				st.append((b // n + 1) % 1000000007)
	elif s == 0:
		pre = [0] * n
		p = 0
		for i in range(n):
			if ls[i] % 2 != 0 and i != n - 1:
				p = p + ls[i] - 1
				pre[i] = p
			else:
				if i == n - 1 and ls[i] % 2 == 0:
					p = p + ls[i] - 1
				else:
					p = p + ls[i]
				pre[i] = p
		for _ in range(I()):
			b = I()
			d = b // n * pre[n - 1]
			if b % n == 0 and ls[n - 1] % 2 == 0:
				st.append((d + 1) % 1000000007)
			elif ls[b % n - 1] % 2 != 0:
				st.append((d + 1 + pre[b % n - 1]) % 1000000007)
			else:
				st.append((d + pre[b % n - 1]) % 1000000007)
	else:
		pre = [0] * n
		p = 0
		for i in range(n):
			if ls[i] == 1:
				pre[i] = p
				if ls[i - 1] % 2 == 0:
					p -= 1
				else:
					p += 1
			elif ls[i] % 2 != 0 and i != n - 1:
				p = p + ls[i] - 1
				pre[i] = p
			elif i == n - 1 and ls[i] % 2 == 0:
				p = p + ls[i] - 1
				pre[i] = p
			else:
				p = p + ls[i]
				pre[i] = p
		for _ in range(I()):
			b = I()
			d = b // n * pre[n - 1]
			if b % n == 0:
				if ls[n - 1] % 2 == 0:
					st.append((d + 1) % 1000000007)
				else:
					st.append(d % 1000000007)
			elif ls[b % n - 1] % 2 != 0:
				st.append((d + 1 + pre[b % n - 1]) % 1000000007)
			else:
				st.append((d + pre[b % n - 1]) % 1000000007)
	print(*st, sep='\n')


import sys
from collections import defaultdict as df

def ini():
	return int(sys.stdin.readline())

def inp():
	return map(int, sys.stdin.readline().strip().split())

def li():
	return list(map(int, sys.stdin.readline().strip().split()))
modulo = 10 ** 9 + 7
for _ in range(ini()):
	n = ini()
	l = li()
	t = l.copy()
	for i in range(n - 1):
		if l[i] & 1 and l[i] != 1:
			l[i] -= 1
	p = [0 for i in range(n)]
	p[0] = l[0]
	for i in range(1, n):
		p[i] += (p[i - 1] + l[i]) % modulo
		p[i] = p[i] % modulo
	if 1 not in l:
		q = ini()
		s = p[n - 1]
		for __ in range(q):
			c = 0
			x = ini()
			q = x // n
			r = x % n
			if l[-1] & 1:
				c += s * q % modulo
				c = c % modulo
			else:
				c += (s * q % modulo - q) % modulo
				c = c % modulo
			if r != 0:
				if r - 2 >= 0:
					c += p[r - 2] % modulo
					c = c % modulo
				c += t[r - 1] % modulo
				c = c % modulo
			elif l[-1] % 2 == 0:
				c += 1
				c = c % modulo
			print(c % modulo)
	else:
		i = l.index(1)
		if i == n - 1:
			q = ini()
			s = p[n - 1]
			for __ in range(q):
				c = 0
				x = ini()
				q = x // n
				r = x % n
				c += s * q % modulo
				c = c % modulo
				if r != 0:
					if r - 2 >= 0:
						c += p[r - 2] % modulo
						c = c % modulo
					c += t[r - 1] % modulo
					c = c % modulo
				print(c % modulo)
		elif i == 0:
			q = ini()
			for __ in range(q):
				c = 0
				x = ini()
				q = x // n
				r = x % n
				c += q % modulo
				c = c % modulo
				if x == 1:
					print(1)
					continue
				if r > 1:
					c += 1
					c = c % modulo
				print(c % modulo)
		else:
			s = p[n - 1]
			s = s % modulo
			if t[i - 1] & 1:
				s += 1
				s = s % modulo
			q = ini()
			for __ in range(q):
				x = ini()
				c = 0
				if x < i + 1:
					c += p[x - 1] % modulo
					if t[x - 1] & 1:
						c += 1 % modulo
						c = c % modulo
					print(c % modulo)
				elif x == i + 1:
					c += p[x - 1] % modulo
					print(c % modulo)
				else:
					q = x // n
					r = x % n
					c += (q * s % modulo - q) % modulo
					if t[i - 1] % 2 == 0:
						c -= q % modulo
					if l[-1] % 2 == 0:
						c -= q % modulo
					if r != 0:
						if r <= i + 1:
							if r - 2 >= 0:
								c += p[r - 2] % modulo
								c = c % modulo
							c += t[r - 1] % modulo
							c = c % modulo
						else:
							if i >= 2:
								c += p[i - 2]
							if t[i - 1] % 2 == 1:
								c += t[i - 1] % modulo
								c = c % modulo
							else:
								c += t[i - 1] - 1
								c = c % modulo
							c += (p[r - 2] - p[i]) % modulo
							c = c % modulo
							c += t[r - 1] % modulo
							c = c % modulo
					elif l[-1] % 2 == 0:
						c += 1
						c = c % modulo
					print(c % modulo)


t = int(input())
for a in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	one = -1
	for i in range(len(A)):
		if A[i] == 1:
			one = i
			break
	once = 0
	if one == -1 or one == n - 1:
		tmp = []
		for i in range(len(A) - 1):
			if A[i] % 2 == 0:
				once += A[i]
				tmp.append(A[i])
			else:
				once += A[i] - 1
				tmp.append(A[i] - 1)
		if A[n - 1] % 2 == 0:
			once += A[n - 1] - 1
			tmp.append(A[n - 1] - 1)
		else:
			once += A[n - 1]
			tmp.append(A[n - 1])
		temp = [tmp[0]]
		for i in range(1, n):
			temp.append(temp[i - 1] + tmp[i])
		q = int(input())
		for i in range(q):
			r = int(input())
			if r == 1:
				ans = A[0]
			else:
				ans = 0
				num = (r - 1) // n
				rem = (r - 1) % n
				ans = num * once
				if rem > 0:
					ans += temp[rem - 1]
				ans += A[rem]
			print(ans % (10 ** 9 + 7))
	elif one == 0:
		q = int(input())
		for i in range(q):
			r = int(input())
			if r == 1:
				ans = A[0]
			else:
				rem = (r - 1) % n
				if rem == 0:
					ans = 1 + (r - 2) // n
				else:
					ans = 1 + (r - 1) // n
			print(ans % (10 ** 9 + 7))
	else:
		tmp = []
		for i in range(len(A) - 1):
			if A[i] % 2 == 0 and i + 1 != one:
				once += A[i]
				tmp.append(A[i])
			elif A[i] % 2 != 0 and i + 1 != one:
				once += A[i] - 1
				tmp.append(A[i] - 1)
			elif A[i] % 2 == 0 and i + 1 == one:
				once += A[i] - 1
				tmp.append(A[i] - 1)
			elif A[i] % 2 != 0 and i + 1 == one:
				once += A[i]
				tmp.append(A[i])
			elif A[i] == 1:
				pass
		if A[n - 1] % 2 == 0:
			once += A[n - 1] - 1
			tmp.append(A[n - 1] - 1)
		else:
			once += A[n - 1]
			tmp.append(A[n - 1])
		temp = [tmp[0]]
		for i in range(1, n):
			temp.append(temp[i - 1] + tmp[i])
		tmp2 = []
		for i in range(len(A) - 1):
			if A[i] % 2 == 0:
				tmp2.append(A[i])
			else:
				tmp2.append(A[i] - 1)
		if A[n - 1] % 2 == 0:
			tmp2.append(A[n - 1] - 1)
		else:
			tmp2.append(A[n - 1])
		temp2 = [tmp2[0]]
		for i in range(1, n):
			temp2.append(temp2[i - 1] + tmp2[i])
		q = int(input())
		for i in range(q):
			r = int(input())
			if r == 1:
				ans = A[0]
			else:
				ans = 0
				num = (r - 1) // n
				rem = (r - 1) % n
				ans = num * once
				if rem > one:
					if rem > 0:
						ans += temp[rem - 1]
					ans += A[rem]
				else:
					if rem > 0:
						ans += temp2[rem - 1]
					ans += A[rem]
			print(ans % (10 ** 9 + 7))


def loop6():
	i = 3
	if i == 3:
		g = 1

def loop5():
	n = int(input())
	ar = list(map(int, input().split()))
	q = int(input())
	sol = [0] * n
	part = ar.copy()
	p = 10 ** 9 + 7
	cnt = 0
	loop6()
	ans = 0
	if ar[0] == 1:
		for i in range(n):
			sol[i] = 1
			cnt = 1
	else:
		for i in range(n):
			if i < n - 1:
				if ar[i] % 2 == 0:
					cnt = (cnt % p + ar[i] % p) % p
					sol[i] = cnt
					part[i] = ar[i]
				elif ar[i] == 1:
					if ar[i - 1] % 2 == 0:
						cnt = (cnt - 1) % p
						part[i - 1] = part[i - 1] - 1
						sol[i - 1] = cnt
						sol[i] = cnt
						part[i] = 0
					else:
						cnt = (cnt + 1) % p
						sol[i - 1] = cnt
						sol[i] = cnt
						part[i - 1] = part[i - 1] + 1
						part[i] = 0
				else:
					cnt = (cnt + ar[i] - 1) % p
					sol[i] = cnt
					part[i] = ar[i] - 1
			elif i == n - 1:
				if ar[i] % 2 == 0:
					cnt += (ar[i] - 1) % p
					sol[i] = cnt
					part[i] = ar[i] - 1
				else:
					cnt = (cnt % p + ar[i] % p) % p
					part[i] = ar[i]
					sol[i] = cnt
	for i in range(q):
		r = int(input())
		if ar[0] == 1:
			if r < n:
				ans = 1
			else:
				g = r // n
				f = r % n
				if f == 1 or f == 0:
					ans = cnt % p * g % p % p
				else:
					ans = cnt % p * g % p % p + 1
		elif r < n:
			ans = sol[r - 1]
			if ar[r - 1] == 1:
				if ar[r - 2] % 2 == 0:
					ans = (sol[r - 1] + 2) % p
			else:
				ans = sol[r - 1] % p
				if part[r - 1] < ar[r - 1]:
					ans = (ans + 1) % p
		else:
			g = r // n
			f = r % n
			if f == 0:
				ans = cnt % p * g % p % p
				if part[-1] < ar[-1]:
					ans = (ans + 1) % p
			else:
				ans = cnt % p * g % p % p
				if ar[f - 1] == 1:
					if ar[f - 2] % 2 == 0:
						ans = (ans % p + (sol[f - 1] + 2) % p) % p
					else:
						ans = (ans % p + sol[f - 1] % p) % p
				else:
					ans = (ans % p + sol[f - 1] % p) % p
					if part[f - 1] < ar[f - 1]:
						ans = (ans + 1) % p
		print(ans)

def diff():
	z = 107
	z1 = 10
	z2 = z1 * z
	for i in range(z):
		z3 = z2 * z1

def loop4():
	loop5()

def loop3():
	loop4()

def loop2():
	loop3()

def loop1():
	loop2()
for _ in range(int(input())):
	diff()
	loop1()


te = int(input())
for tt in range(te):
	n = int(input())
	a = list(map(int, input().split()))
	aa = [0] * n
	z = 0
	s = 0
	t = 0
	ss = [0] * n
	if a[0] == 1:
		z = 1
		ss[0] = 1
		s1 = 1
	else:
		p = -1
		for i in range(n):
			if a[i] == 1:
				p = i
				break
		for i in range(n - 1):
			if i == p - 1:
				if p != n - 1:
					if a[i] % 2 == 0:
						s = (s + a[i] - 1) % 1000000007
						aa[i] = a[i] - 1
					else:
						s = (s + a[i]) % 1000000007
						aa[i] = a[i]
				elif a[i] % 2 == 1:
					s = (s + a[i] - 1) % 1000000007
					aa[i] = a[i] - 1
				else:
					s = (s + a[i]) % 1000000007
					aa[i] = a[i]
			elif i == p:
				aa[i] = a[i] - 1
				t = 1
			elif a[i] % 2 == 1:
				s = (s + a[i] - 1) % 1000000007
				aa[i] = a[i] - 1
			else:
				s = (s + a[i]) % 1000000007
				aa[i] = a[i]
			ss[i] = s
	if a[n - 1] == 1:
		s = (s + a[n - 1]) % 1000000007
		aa[n - 1] = 0
	elif a[n - 1] % 2 == 1:
		s = (s + a[n - 1]) % 1000000007
		aa[n - 1] = a[n - 1]
	else:
		s = (s + a[n - 1] - 1) % 1000000007
		aa[n - 1] = a[n - 1] - 1
	ss[n - 1] = s
	s1 = s
	s2 = t
	q = int(input())
	for i in range(q):
		r = int(input())
		if z == 1:
			rr = r // n
			r = r % n
			if r > 1 and rr > 0 or rr == 0:
				rr += 1
			print(rr % 1000000007)
			continue
		s = 0
		if r >= n:
			s = s1 * (r // n) % 1000000007
			r = r % n
		if r > 0:
			s = (s + ss[r - 1]) % 1000000007
		if aa[r - 1] != a[r - 1]:
			s = s - aa[r - 1] + a[r - 1]
		if a[r - 1] == 1:
			if a[r - 2] % 2 == 0:
				if r == 0:
					s -= 1
				else:
					s += 1
			else:
				s -= 1
		print(s % 1000000007)


modulo = 1000000007
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = -1
	index = -1
	if 1 in arr:
		index = arr.index(1)
	if index == -1 or index == n - 1:
		ans = 0
		temp_arr = []
		for i in range(n - 1):
			if arr[i] % 2 == 1:
				ans += arr[i] - 1
				temp_arr.append(ans)
			else:
				ans += arr[i]
				temp_arr.append(ans)
		if arr[-1] % 2 == 0:
			ans += arr[-1] - 1
		else:
			ans += arr[-1]
		for _ in range(int(input())):
			r = int(input())
			if r % n == 0:
				if arr[-1] % 2 == 0:
					print((r // n * ans + 1) % modulo)
				else:
					print(r // n * ans % modulo)
			elif arr[r % n - 1] % 2 == 1:
				print((r // n * ans + temp_arr[r % n - 1] + 1) % modulo)
			else:
				print((r // n * ans + temp_arr[r % n - 1]) % modulo)
	elif index == 0:
		for _ in range(int(input())):
			r = int(input())
			if r % n == 0:
				print(r // n % modulo)
			elif r % n == 1 and r > n:
				print(r // n % modulo)
			else:
				print((r // n + 1) % modulo)
		continue
	else:
		ans = 0
		temp_arr = []
		for i in range(n - 1):
			if i != index - 1:
				if arr[i] % 2 == 0:
					ans += arr[i]
				else:
					ans += arr[i] - 1
			elif arr[i] % 2 == 0:
				ans += arr[i] - 1
			else:
				ans += arr[i]
			temp_arr.append(ans)
		if arr[-1] % 2 == 0:
			ans += arr[-1] - 1
		else:
			ans += arr[-1]
		for _ in range(int(input())):
			r = int(input())
			if r % n == 0:
				if arr[-1] % 2 == 0:
					print((r // n * ans + 1) % modulo)
				else:
					print(r // n * ans % modulo)
			elif index == r % n - 1:
				if arr[index - 1] % 2 == 0:
					print((r // n * ans + temp_arr[r % n - 1] + 2) % modulo)
				else:
					print((r // n * ans + temp_arr[r % n - 1]) % modulo)
			elif index - 1 == r % n - 1:
				if arr[index - 1] % 2 == 0:
					print((r // n * ans + temp_arr[r % n - 1] + 1) % modulo)
				else:
					print((r // n * ans + temp_arr[r % n - 1]) % modulo)
			elif arr[r % n - 1] % 2 == 1:
				print((r // n * ans + temp_arr[r % n - 1] + 1) % modulo)
			else:
				print((r // n * ans + temp_arr[r % n - 1]) % modulo)


mod = 1000000007
t = int(input())
for T in range(t):
	size = int(input())
	templ1 = list(map(int, input().split()))
	qsize = int(input())
	if 1 not in templ1:
		res = []
		tes = 0
		for j in range(size - 1):
			if templ1[j] % 2 == 1:
				tes = (tes + (templ1[j] - 1)) % mod
			else:
				tes = (tes + templ1[j]) % mod
			res.append(tes)
		if templ1[-1] % 2 == 1:
			tes = (tes + templ1[-1]) % mod
		else:
			tes = (tes + (templ1[-1] - 1)) % mod
		res.append(tes)
		for i in range(qsize):
			query = int(input())
			tes1 = query // size * tes % mod
			md = query % size
			if md == 0:
				if templ1[-1] % 2 == 0:
					tes1 = (tes1 + 1) % mod
			else:
				tes1 = (tes1 + res[md - 1]) % mod
				if templ1[md - 1] % 2 == 1:
					tes1 = (tes1 + 1) % mod
			print(tes1 % mod)
	elif templ1[0] == 1:
		for i in range(qsize):
			query = int(input())
			tes = query // size % mod
			if query % size > 1 or query < size:
				tes = (tes + 1) % mod
			print(tes % mod)
	elif templ1[-1] == 1:
		res = []
		tes = 0
		for i in range(size - 1):
			if templ1[i] % 2 == 1:
				tes = (tes + (templ1[i] - 1)) % mod
			else:
				tes = (tes + templ1[i]) % mod
			res.append(tes)
		tes = (tes + 1) % mod
		res.append(tes)
		for i in range(qsize):
			query = int(input())
			tes1 = query // size * tes % mod
			md = query % size
			if md != 0:
				tes1 = tes1 + res[md - 1]
				if templ1[md - 1] % 2 != 0:
					tes1 = (tes1 + 1) % mod
			print(tes1 % mod)
	else:
		res = []
		tp = templ1.index(1)
		tes1 = 0
		for j in range(tp - 1):
			if templ1[j] % 2 == 1:
				tes1 = (tes1 + (templ1[j] - 1)) % mod
			else:
				tes1 = (tes1 + templ1[j]) % mod
			res.append(tes1)
		if templ1[tp - 1] % 2 == 1:
			tes4 = (tes1 + (templ1[tp - 1] - 1)) % mod
			tes1 = (tes1 + templ1[tp - 1]) % mod
		else:
			tes4 = (tes1 + templ1[tp - 1]) % mod
			tes1 = (tes1 + (templ1[tp - 1] - 1)) % mod
		res.append(tes1)
		res.append(tes4 + 1)
		for j in range(tp + 1, size - 1):
			if templ1[j] % 2 == 1:
				tes1 = (tes1 + (templ1[j] - 1)) % mod
			else:
				tes1 = (tes1 + templ1[j]) % mod
			res.append(tes1)
		if templ1[-1] % 2 == 1:
			tes1 = (tes1 + templ1[-1]) % mod
		else:
			tes1 = (tes1 + (templ1[-1] - 1)) % mod
		res.append(tes1)
		for i in range(qsize):
			query = int(input())
			tes = tes1 * (query // size) % mod
			md = query % size
			if md - 1 < tp:
				if md == 0:
					if templ1[-1] % 2 == 0:
						tes = (tes + 1) % mod
				else:
					if md - 2 > -1:
						tes = (tes + res[md - 2]) % mod
					tes = (tes + templ1[md - 1]) % mod
			elif md - 1 == tp:
				tes = (tes + res[md - 1]) % mod
			else:
				tes = (tes + res[md - 1]) % mod
				if templ1[md - 1] % 2 != 0:
					tes = (tes + 1) % mod
			print(tes % mod)


o = 1000000007

def func2(a, n):
	sm = 0
	s = [0] * (n + 1)
	for i in range(n - 1):
		if i == ind - 1:
			if a[i] % 2 == 0:
				sm = sm + a[i] - 1
				s[i] = sm
			else:
				sm += a[i]
				s[i] = sm
		elif a[i] % 2 == 0:
			sm += a[i]
			s[i] = sm
		else:
			sm += a[i] - 1
			s[i] = sm
	if a[n - 1] % 2 == 0:
		sm += a[n - 1] - 1
	else:
		sm += a[n - 1]
	q = int(input())
	for _ in range(q):
		p = int(input())
		if p % n == 0:
			if a[n - 1] % 2 == 0:
				print((p // n * sm + 1) % o)
			else:
				print(p // n * sm % o)
		else:
			l = p % n
			if ind == l - 1:
				if a[ind - 1] % 2 == 0:
					an = (p // n * sm + 2 + s[l - 1]) % o
					print(an)
				else:
					an = (p // n * sm + s[l - 1]) % o
					print(an)
			elif ind == l:
				if a[ind - 1] % 2 == 0:
					an = (p // n * sm + s[l - 1] + 1) % o
					print(an)
				else:
					an = (p // n * sm + s[l - 1]) % o
					print(an)
			elif a[l - 1] % 2 != 0:
				an = (p // n * sm + s[l - 1] + 1) % o
				print(an)
			else:
				an = (p // n * sm + s[l - 1]) % o
				print(an)

def fun3(a, n):
	sm = 0
	s = [0] * (n + 1)
	for i in range(n):
		if i == n - 1:
			if a[i] % 2 == 0:
				sm += a[i] - 1
			else:
				sm += a[i]
		elif a[i] % 2 == 0:
			sm += a[i]
			s[i] = sm
		else:
			sm += a[i] - 1
			s[i] = sm
	q = int(input())
	for _ in range(q):
		p = int(input())
		l = p % n
		if l == 0:
			if a[n - 1] % 2 == 0:
				print((p // n * sm + 1) % o)
			else:
				print(p // n * sm % o)
		elif a[l - 1] % 2 != 0:
			print((p // n * sm + s[l - 1] + 1) % o)
		else:
			print((p // n * sm + s[l - 1]) % o)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	v = 0
	if a[0] == 1:
		v = 1
	else:
		for i in range(n):
			if a[i] == 1 and i != n - 1:
				v = 2
				ind = i
				break
	if v == 1:
		q = int(input())
		for _ in range(q):
			p = int(input())
			if p <= n:
				print(1)
			elif p % n == 0:
				print(p // n % o)
			elif p % n == 1:
				print(p // n % o)
			else:
				print((p // n + 1) % o)
	elif v == 2:
		func2(a, n)
	else:
		fun3(a, n)


import math
from collections import deque as queue

def Sie(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans
sz = 3 * 10 ** 5
tree = [[] for i in range(sz)]
vis = [False] * sz
path = [[] for i in range(sz)]

def Sie(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def addEdge(a, b):
	tree[a].append(b)
	tree[b].append(a)

def Sie(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def bfs(node):
	qu = queue()
	qu.append([node, -1])
	vis[node] = True
	while len(qu) > 0:
		p = qu.popleft()
		vis[p[0]] = True
		for child in tree[p[0]]:
			if vis[child] == False:
				qu.append([child, p[0]])
				for u in path[p[0]]:
					path[child].append(u)
				path[child].append(p[0])

def Sie(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def displayPath(node):
	ans = path[node]
	av = []
	for k in ans:
		av.append(k)
	av.append(node)
	return av
mmm = 10 ** 9 + 7
for _ in range(int(input())):
	aaaaa = 0
	n = int(input())
	l1 = list(map(int, input().split()))
	l = list(l1)
	aaaaa = 0
	q = int(input())
	if n == 1:
		aaaaa = 0
		if 1 in l:
			for i in range(q):
				r = int(input())
				print(r % mmm)
				aaaaa = 0
		else:
			for i in range(q):
				aaaaa = 0
				r = int(input())
				aaaaa = 0
				if l[0] % 2 == 0:
					aaaaa = 0
					r = r * (l[0] - 1) + 1
				else:
					aaaaa = 0
					r = r * l[0]
				print(r % mmm)
	elif 1 in l:
		if l[-1] == 1:
			aaaaa = 0
			if l[0] % 2 != 0:
				l[0] -= 1
			for i in range(1, n):
				if l[i] % 2 != 0 and i != n - 1:
					l[i] -= 1
				l[i] += l[i - 1]
				aaaaa = 0
			for i in range(q):
				r = int(input())
				r1 = r // n * l[-1]
				r2 = l[r % n - 1]
				aaaaa = 0
				if r % n == 0 and l1[-1] % 2 != 0:
					r2 = 0
				elif r % n == 0 and l1[-1] % 2 == 0:
					r2 = 1
				elif l1[r % n - 1] % 2 != 0 and r % n != 0:
					r2 += 1
				print((r1 + r2) % mmm)
		elif l[0] == 1:
			aaaaa = 0
			for i in range(q):
				r = int(input())
				if r % n == 1:
					r = r // n
				else:
					r = int(math.ceil(r / n))
				if r == 0:
					r = 1
				print(r % mmm)
		else:
			aaaaa = 0
			for i in range(1, n):
				if l[i] == 1:
					if l[i - 1] % 2 == 0:
						l[i - 1] -= 1
					break
			for i in range(0, n - 1):
				aaaaa = 0
				if l[i] % 2 != 0 and l[i + 1] != 1 and (l[i] != 1):
					l[i] -= 1
			if l[-1] % 2 == 0:
				l[-1] -= 1
			for i in range(1, n):
				if l[i] == 1 and i != n - 1:
					l[i] = l[i - 1]
				else:
					l[i] += l[i - 1]
			for i in range(q):
				r = int(input())
				r1 = r // n * l[-1]
				r2 = l[r % n - 1]
				if r % n == 0 and l1[-1] % 2 != 0:
					r2 = 0
				elif r % n == 0 and l1[-1] % 2 == 0:
					r2 = 1
				elif l1[r % n - 1] == 1:
					if l1[r % n - 2] % 2 == 0:
						r2 += 2
					else:
						r2 + 1
				elif l1[r % n - 1] % 2 != 0 and r % n != 0 and (l1[r % n] != 1) or (l1[r % n] == 1 and l1[r % n - 1] % 2 == 0):
					r2 += 1
				print((r1 + r2) % mmm)
	else:
		if l[-1] % 2 == 0:
			l[-1] -= 1
		if l[0] % 2 != 0:
			l[0] -= 1
		for i in range(1, n):
			if l[i] % 2 != 0 and i != n - 1:
				l[i] -= 1
			l[i] += l[i - 1]
		for i in range(q):
			r = int(input())
			r1 = r // n * l[-1]
			r2 = l[r % n - 1]
			if r % n == 0 and l1[-1] % 2 != 0:
				r2 = 0
			elif r % n == 0 and l1[-1] % 2 == 0:
				r2 = 1
			elif l1[r % n - 1] % 2 != 0 and r % n != 0:
				r2 += 1
			print((r1 + r2) % mmm)
from collections import deque as queue

def Sie(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans
sz = 3 * 10 ** 5
tree = [[] for i in range(sz)]
vis = [False] * sz
path = [[] for i in range(sz)]

def Sie(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def addEdge(a, b):
	tree[a].append(b)
	tree[b].append(a)

def Sie(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def bfs(node):
	qu = queue()
	qu.append([node, -1])
	vis[node] = True
	while len(qu) > 0:
		p = qu.popleft()
		vis[p[0]] = True
		for child in tree[p[0]]:
			if vis[child] == False:
				qu.append([child, p[0]])
				for u in path[p[0]]:
					path[child].append(u)
				path[child].append(p[0])

def Sie(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def displayPath(node):
	ans = path[node]
	av = []
	for k in ans:
		av.append(k)
	av.append(node)
	return av


modu = pow(10, 9) + 7
for i in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	chef = [0] * n
	if arr[0] == 1:
		chef[0] = 1
	else:
		for j in range(n):
			if j == n - 1:
				chef[j] = arr[j] - 1 + arr[j] % 2
			elif arr[j] == 1:
				chef[j - 1] = arr[j - 1] - 1 + arr[j - 1] % 2
				chef[j] = 0
			else:
				chef[j] = arr[j] - arr[j] % 2
	summ = sum(chef)
	sums = [0] * (n + 1)
	sums[0]
	for i in range(1, n + 1):
		sums[i] = sums[i - 1] + chef[i - 1]
	for q in range(int(input())):
		r = int(input())
		if arr[0] == 1:
			if r % n == 1 and r > n:
				ans = summ * round(int(r / n))
			else:
				ans = summ * round(int((r - 1) / n)) + 1
		elif r % n:
			if chef[r % n - 1] == 0:
				ans = summ * round(int(r / n)) + sums[r % n - 2] + arr[r % n - 2] - arr[r % n - 2] % 2 + arr[r % n - 1]
			else:
				ans = summ * round(int(r / n)) + sums[r % n - 1] + arr[r % n - 1]
		else:
			ans = summ * round(int(r / n)) - chef[n - 1] + arr[n - 1]
		ans = ans % modu
		print(ans)


t = int(input())
(n, a, sum) = (0, [], [])

def geteven(x):
	if x & 1:
		return x - 1
	else:
		return x

def getodd(x):
	if x & 1:
		return x
	else:
		return x - 1

def start1():
	if n == 1:
		return r
	if r <= n:
		return 1
	if (r - 1) % n == 0:
		return (r - 1) // n
	else:
		return (r - 1) // n + 1

def lessthanN(r):
	if r == 0:
		return 0
	if a[r - 1] == 1:
		return sum[r - 2] + geteven(a[r - 2]) + 1
	else:
		return sum[r - 1] + a[r - 1]

def normal(r):
	if r <= n:
		return lessthanN(r)
	ans = r // n
	if n == 1:
		ans = sum[1] * (ans - 1) + a[0]
	elif r % n == 0:
		ans = sum[n] * (ans - 1) + sum[n - 1] + a[n - 1]
	else:
		ans = sum[n] * ans
		ans += lessthanN(r % n)
	return ans
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	sum = [0] * (n + 1)
	for i in range(1, n + 1):
		if i == n:
			sum[i] = getodd(a[i - 1])
		elif a[i - 1] != 1:
			if a[i] == 1 and i + 1 != n:
				sum[i] = getodd(a[i - 1])
			else:
				sum[i] = geteven(a[i - 1])
		sum[i] = sum[i - 1] + sum[i]
	q = int(input())
	while q > 0:
		r = int(input())
		ans = 0
		if a[0] == 1:
			ans = start1()
		else:
			ans = normal(r)
		print(ans % 1000000007)
		q -= 1
	t -= 1


for Z in range(int(input())):
	(N, lst) = (int(input()), list(map(int, input().split(' '))))
	(dp, mod, temp) = ([0] * N, int(1000000000.0 + 7), [0] * N)
	if N == 1:
		dp[0] = lst[0] - int(lst[0] % 2 == 0)
		temp[0] = temp[0] + int(lst[0] % 2 == 0)
	elif lst[0] == 1:
		dp = [1] * N
	elif 1 not in lst or lst.index(1) == N - 1:
		dp[0] = lst[0] - int(lst[0] & 1)
		temp[0] = temp[0] + int(lst[0] & 1)
		for i in range(1, N - 1):
			dp[i] = (dp[i - 1] + lst[i] - int(lst[i] & 1)) % mod
			temp[i] = temp[i] + int(lst[i] & 1)
		dp[N - 1] = (dp[N - 2] + lst[N - 1] - int(lst[N - 1] % 2 == 0)) % mod
		temp[N - 1] = temp[N - 1] + int(lst[N - 1] % 2 == 0)
	else:
		if lst[1] == 1:
			dp[0] = lst[0] - int(lst[0] % 2 == 0)
			temp[0] = temp[0] + int(lst[0] % 2 == 0)
			temp[1] = temp[1] + 1 if lst[0] % 2 == 0 else temp[1] - 1
		else:
			dp[0] = lst[0] - int(lst[0] & 1)
			temp[0] = temp[0] + int(lst[0] & 1)
		for i in range(1, N - 1):
			if lst[i + 1] == 1:
				dp[i] = (dp[i - 1] + lst[i] - int(lst[i] % 2 == 0)) % mod
				temp[i] = temp[i] + int(lst[i] % 2 == 0)
				temp[i + 1] = temp[i + 1] + 1 if lst[i] % 2 == 0 else temp[i + 1] - 1
			else:
				dp[i] = (dp[i - 1] + lst[i] - int(lst[i] & 1)) % mod
				temp[i] = temp[i] + int(lst[i] & 1)
		dp[N - 1] = (dp[N - 2] + lst[N - 1] - int(lst[N - 1] % 2 == 0)) % mod
		temp[N - 1] = temp[N - 1] + int(lst[N - 1] % 2 == 0)
	for _ in range(int(input())):
		R = int(input()) - 1
		(ans, index) = ((R // N * dp[-1] % mod + (dp[R % N] + temp[R % N]) % mod) % mod, R % N)
		print(ans - 1 if index == 0 and lst[index] == 1 and (R >= N) and (N > 1) else ans)


t = input()
a = int(t)
for __ in range(a):
	p = 10 ** 9 + 7
	cnt = 0
	ans = 0
	m = input()
	n = int(m)
	arrp = []
	arr = list(map(int, input().split()))
	for i in arr:
		arrp.append(i)
	sol = []
	for i in range(n):
		sol.append(0)
	if arr[0] == 1:
		for i in range(n):
			sol[i] = 1
			cnt = 1
	else:
		for i in range(n):
			if i < n - 1:
				if arr[i] % 2 == 0:
					cnt = (cnt % p + arr[i] % p) % p
					sol[i] = cnt
					arrp[i] = arr[i]
				elif arr[i] == 1:
					if arr[i - 1] % 2 == 0:
						cnt = (cnt - 1) % p
						arrp[i - 1] = arrp[i - 1] - 1
						sol[i - 1] = cnt
						sol[i] = cnt
						arrp[i] = 0
					else:
						cnt = (cnt + 1) % p
						sol[i - 1] = cnt
						sol[i] = cnt
						arrp[i - 1] = arrp[i - 1] + 1
						arrp[i] = 0
				else:
					cnt = (cnt % p + arr[i] % p - 1) % p
					sol[i] = cnt
					arrp[i] = arr[i] - 1
			elif i == n - 1:
				if arr[i] % 2 == 0:
					cnt += (arr[i] - 1) % p
					sol[i] = cnt
					arrp[i] = arr[i] - 1
				else:
					cnt = (cnt % p + arr[i] % p) % p
					arrp[i] = arr[i]
					sol[i] = cnt
	Q = input()
	q = int(Q)
	for i in range(q):
		R = input()
		r = int(R)
		if arr[0] == 1:
			if r < n:
				ans = 1
			else:
				g = r // n
				f = r % n
				if f == 1 or f == 0:
					ans = cnt % p * g % p % p
				else:
					ans = cnt % p * g % p % p + 1
		elif r < n:
			ans = sol[r - 1]
			if arr[r - 1] == 1:
				if arr[r - 2] % 2 == 0:
					ans = (sol[r - 1] + 2) % p
			else:
				ans = sol[r - 1] % p
				if arrp[r - 1] < arr[r - 1]:
					ans = (ans + 1) % p
		else:
			g = r // n
			f = r % n
			if f == 0:
				ans = cnt % p * g % p % p
				if arrp[-1] < arr[-1]:
					ans = (ans + 1) % p
			else:
				ans = cnt % p * g % p % p
				if arr[f - 1] == 1:
					if arr[f - 2] % 2 == 0:
						ans = (ans % p + (sol[f - 1] + 2) % p) % p
					else:
						ans = (ans % p + sol[f - 1] % p) % p
				else:
					ans = (ans % p + sol[f - 1] % p) % p
					if arrp[f - 1] < arr[f - 1]:
						ans = (ans + 1) % p
		print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	q = int(input())
	l1 = [[0, 0]]
	for j in range(n):
		if j < n - 1:
			if l[j + 1] != 1 or j == n - 2:
				l1.append([l1[len(l1) - 1][0] + (l[j] - l[j] % 2), l[j] % 2])
			else:
				l1.append([l1[len(l1) - 1][0] + (l[j] + l[j] % 2 - 1), 1 - l[j] % 2])
		else:
			l1.append([l1[len(l1) - 1][0] + (l[j] + l[j] % 2 - 1), 1 - l[j] % 2])
	l1.pop(0)
	for k in range(q):
		r = int(input())
		a = r // n
		if l[0] == 1:
			if a == 0:
				print(1)
			elif r % n == 0:
				print(a % 1000000007)
			elif r % n == 1:
				print(a % 1000000007)
			else:
				print((a + 1) % 1000000007)
		else:
			b = r % n
			if b != 0:
				if l[b - 1] != 1:
					s = l1[len(l1) - 1][0] * a + l1[b - 1][0] + l1[b - 1][1]
				else:
					s = l1[len(l1) - 1][0] * a + l1[b - 1][0] + l1[b - 2][1] * 2
			else:
				s = l1[len(l1) - 1][0] * a + l1[len(l1) - 1][1]
			print(s % 1000000007)


try:
	t = int(input())
	for _ in range(t):
		queries = []
		n = int(input())
		arr = list(map(int, input().split()))
		q = int(input())
		for a in range(q):
			r = int(input())
			queries.append(r)
		value = 0
		test = [0] * n
		err = 10 ** 9 + 7
		x = 0
		if n > 1:
			if arr[0] != 1:
				for i in range(n):
					if arr[i] % 2 == 0:
						if i == n - 1:
							test[i] = arr[i] + x - 1
							x = test[i]
						elif i < n - 2 and arr[i + 1] == 1:
							test[i] = arr[i] + x - 1
							x = test[i]
						else:
							test[i] = arr[i] + x
							x = test[i]
					elif i == n - 1:
						test[i] = arr[i] + x
						x = test[i]
					elif i < n - 2 and arr[i + 1] == 1:
						test[i] = arr[i] + x
						x = test[i]
					else:
						test[i] = arr[i] + x - 1
						x = test[i]
		for j in range(q):
			if n == 1:
				if arr[0] % 2 == 1:
					value = queries[j] * arr[0] % err
				else:
					value = (queries[j] * arr[0] - queries[j] + 1) % err
			elif arr[0] == 1:
				div = queries[j] // n
				rem = queries[j] % n
				if queries[j] == 1:
					value = 1
				elif rem < 2:
					value = div % err
				else:
					value = (div + 1) % err
			else:
				div = queries[j] // n
				rem = queries[j] % n
				if rem == 0:
					if arr[-1] % 2 == 0:
						value = (div * test[-1] + 1) % err
					elif arr[-1] % 2 == 1:
						value = div * test[-1] % err
				elif arr[rem] == 1 and rem == n - 1 and (arr[rem - 1] % 2 == 1):
					value = (div * test[-1] + test[rem - 1] + 1) % err
				elif arr[rem - 1] == 1 and arr[rem - 2] % 2 == 0:
					value = (div * test[-1] + test[rem - 1] + 2) % err
				elif (arr[rem] == 1 or arr[rem - 1] == 1) and arr[rem - 1] % 2 == 1:
					value = (div * test[-1] + test[rem - 1]) % err
				elif arr[rem] == 1 and arr[rem - 1] % 2 == 0 and (rem != n - 1):
					value = (div * test[-1] + test[rem - 1] + 1) % err
				elif arr[rem] == 1 and arr[rem - 1] % 2 == 0:
					value = (div * test[-1] + test[rem - 1]) % err
				elif arr[rem - 1] % 2 == 0:
					value = (div * test[-1] + test[rem - 1]) % err
				elif arr[rem - 1] % 2 == 1:
					value = (div * test[-1] + test[rem - 1] + 1) % err
			print(value)
except EOFError:
	pass


m = 10 ** 9 + 7
t = int(input())
for testcase in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	pos1 = -1
	if n == 1:
		q = int(input())
		for qq in range(q):
			r = int(input())
			if a[0] % 2 == 1:
				print(r * a[0] % m)
			else:
				print((r * (a[0] - 1) % m + 1) % m)
	elif a[0] == 1:
		pos1 = 0
		q = int(input())
		for qq in range(q):
			r = int(input())
			full = r // n
			part = r % n
			res = full % m
			if part > 1:
				res = (res + 1) % m
			elif part == 1 and full == 0:
				res = (res + 1) % m
			print(res)
	elif a[-1] == 1:
		pos1 = n - 1
		fscore = 0
		sums = []
		for i in range(n - 1):
			if a[i] % 2 == 0:
				fscore = (fscore + a[i]) % m
			else:
				fscore = (fscore + a[i] - 1) % m
			sums.append(fscore)
		fscore = (fscore + 1) % m
		sums.append(fscore)
		q = int(input())
		for qq in range(q):
			r = int(input())
			full = r // n
			part = r % n
			res = full * fscore % m
			if part == 1:
				res = (res + a[0]) % m
			elif part > 1:
				res = (res + (sums[part - 2] + a[part - 1]) % m) % m
			print(res)
	else:
		fscore = 0
		fscore_end = 0
		sums = []
		partpos = 0
		for i in range(n - 1):
			if a[i] == 1:
				pos1 = i
				if a[i - 1] % 2 == 1:
					partpos = (sums[i - 1] + 1) % m
					sums[i - 1] = (sums[i - 1] + 1) % m
					fscore = (fscore + 1) % m
				else:
					partpos = (sums[i - 1] + 1) % m
					sums[i - 1] -= 1
					fscore -= 1
			if a[i] % 2 == 0:
				fscore = (fscore + a[i]) % m
			else:
				fscore = (fscore + a[i] - 1) % m
			sums.append(fscore)
		if a[-1] % 2 == 1:
			fscore = (fscore + a[-1]) % m
		else:
			fscore = (fscore + a[-1] - 1) % m
			fscore_end = 1
		sums.append(fscore)
		if pos1 != -1:
			q = int(input())
			for qq in range(q):
				r = int(input())
				full = r // n
				part = r % n
				res = 0
				if part == 0:
					res = (full * fscore % m + fscore_end) % m
				else:
					res = full * fscore % m
					if part == 1:
						res = (res + a[0]) % m
					elif part - 1 == pos1:
						res = (res + partpos) % m
					else:
						res = ((res + sums[part - 2]) % m + a[part - 1]) % m
				print(res)
		else:
			q = int(input())
			for qq in range(q):
				r = int(input())
				full = r // n
				part = r % n
				res = 0
				if part == 0:
					res = (full * fscore % m + fscore_end) % m
				else:
					res = full * fscore % m
					if part == 1:
						res = (res + a[0]) % m
					else:
						res = ((res + sums[part - 2]) % m + a[part - 1]) % m
				print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a = [0] + a
	dp = [0] * 100005
	s = 0
	if a[1] != 1:
		for i in range(1, n + 1):
			if a[i] & 1:
				dp[i] = (s + a[i] - 1) % 1000000007
			else:
				dp[i] = (s + a[i]) % 1000000007
			if i <= n - 2 and a[i + 1] == 1 or i == n:
				if a[i] & 1:
					s = (s + a[i]) % 1000000007
				else:
					s = (s + a[i] - 1) % 1000000007
			elif a[i] & 1:
				s = (s + a[i] - 1) % 1000000007
			else:
				s = (s + a[i]) % 1000000007
			if i == n:
				dp[i] = s
		q = int(input())
		for _ in range(q):
			r = int(input())
			A = 0
			A = s * (r // n) % 1000000007
			if r % n == 0:
				A = (A - s + 1000000007) % 1000000007
				r = n
			else:
				r = r - r // n * n
			A = (A + dp[r - 1] + a[r]) % 1000000007
			print(A)
	else:
		q = int(input())
		for _ in range(q):
			r = int(input())
			A = 0
			A += (r - 1) // n + 1
			temp = r - n * (r // n)
			if temp == 1:
				A -= 1
			A = A % 1000000007
			if r == 1:
				A = 1
			print(A)


def getCandies(data, s, k):
	if k < len(data):
		if data[k - 1] % 2 == 0:
			return s[k - 1]
		else:
			return s[k - 1] + 1
	if k == len(data):
		if data[-1] % 2 == 0:
			return s[-1] + 1
		else:
			return s[-1]
	else:
		rem = k % len(data)
		t = k // len(data)
		if rem == 0 and data[-1] % 2 == 0:
			return (t - 1) * s[-1] + s[-1] + 1
		if rem == 0 and data[-1] % 2 != 0:
			return t * s[-1]
		if data[-1] % 2 == 0:
			if data[rem - 1] % 2 == 0:
				return t * s[-1] + s[rem - 1]
			else:
				return t * s[-1] + s[rem - 1] + 1
		elif data[rem - 1] % 2 == 0:
			return t * s[-1] + s[rem - 1]
		else:
			return t * s[-1] + s[rem - 1] + 1

def getCandies2(data, k):
	if k < len(data):
		return 1
	else:
		rem = k % len(data)
		t = k // len(data)
		if rem == 0:
			return t
		elif rem == 1:
			return t
		else:
			return t + 1

def getCandies3(s, k, data, ind):
	if k < len(data):
		if k - 1 < ind:
			if data[k - 1] % 2 == 0:
				return s[k - 1]
			else:
				return s[k - 1] + 1
		elif k - 1 == ind:
			if data[ind - 1] % 2 == 0:
				return s[ind - 1] + 1
			else:
				return s[ind - 1] + 1
		elif data[ind - 1] % 2 == 0:
			if data[k - 1] % 2 == 0:
				return s[ind - 1] + s[k - 1] - 1
			else:
				return s[ind - 1] + s[k - 1]
		elif data[k - 1] % 2 == 0:
			return s[ind - 1] + s[k - 1] + 1
		else:
			return s[ind - 1] + s[k - 1] + 2
	if k > len(data):
		rem = k % len(data)
		temp = k // len(data)
		ans = 0
		if data[-1] % 2 == 0:
			if data[ind - 1] % 2 == 0:
				if rem == 0:
					ans += temp * (s[ind - 1] + s[-1] - 1) + 1
				else:
					ans += temp * (s[ind - 1] + s[-1] - 1)
			elif rem == 0:
				ans += temp * (s[ind - 1] + s[-1] + 1) + 1
			else:
				ans += temp * (s[ind - 1] + s[-1] + 1)
		elif data[ind - 1] % 2 == 0:
			ans += temp * (s[ind - 1] + s[-1] - 1)
		else:
			ans += temp * (s[ind - 1] + s[-1] + 1)
		if rem == 0:
			return ans
		if rem - 1 < ind:
			if data[rem - 1] % 2 == 0:
				return ans + s[rem - 1]
			else:
				return ans + s[rem - 1] + 1
		elif rem - 1 == ind:
			if data[ind - 1] % 2 == 0:
				return ans + s[ind - 1] + 1
			else:
				return ans + s[ind - 1] + 1
		elif data[ind - 1] % 2 == 0:
			if data[rem - 1] % 2 == 0:
				return ans + s[ind - 1] + s[rem - 1] - 1
			else:
				return ans + s[ind - 1] + s[rem - 1]
		elif data[rem - 1] % 2 == 0:
			return ans + s[ind - 1] + s[rem - 1] + 1
		else:
			return ans + s[ind - 1] + s[rem - 1] + 2
	if k == len(data):
		if data[ind - 1] % 2 == 0:
			if data[-1] % 2 == 0:
				return s[ind - 1] + s[-1]
			else:
				return s[ind - 1] + s[-1] - 1
		elif data[-1] % 2 == 0:
			return s[ind - 1] + s[-1] + 2
		else:
			return s[ind - 1] + s[-1] + 1

def getCandies4(data, k):
	if data[0] % 2 == 0:
		return (k - 1) * (data[0] - 1) + data[0]
	else:
		return k * data[0]

def getSum(data):
	if len(data) == 1:
		return ([data[0]], -1, 'c1')
	if data[0] % 2 == 0:
		s = [data[0]]
	else:
		s = [data[0] - 1]
	ind = None
	if data[0] == 1:
		return (0, 0, 'c2')
	if data[-1] == 1:
		for i in range(1, len(data) - 1):
			if data[i] % 2 == 0:
				t = s[-1] + data[i]
				s.append(t)
			else:
				t = s[-1] + data[i] - 1
				s.append(t)
		s.append(s[-1] + 1)
		return (s, len(data) - 1, 'c3')
	flag = 0
	for i in range(1, len(data) - 1):
		if data[i] == 1:
			s.append(1)
			ind = i
			continue
		elif ind is None:
			if data[i] % 2 == 0:
				t = s[-1] + data[i]
			else:
				t = s[-1] + data[i] - 1
			s.append(t)
		elif flag == 0:
			flag = 1
			if data[i] % 2 == 0:
				s.append(data[i])
			else:
				s.append(data[i] - 1)
		else:
			if data[i] % 2 == 0:
				t = s[-1] + data[i]
			else:
				t = s[-1] + data[i] - 1
			s.append(t)
	if data[-1] % 2 == 0 and s[-1] != 1:
		s.append(s[-1] + data[-1] - 1)
	elif data[-1] % 2 != 0 and s[-1] != 1:
		s.append(s[-1] + data[-1])
	elif data[-1] % 2 == 0:
		s.append(data[-1] - 1)
	else:
		s.append(data[-1])
	return (s, ind, 'c4')
ret = []
t = int(input())
for i in range(t):
	n = int(input())
	data = [int(i) for i in input().split()]
	(s, ind, c) = getSum(data)
	q = int(input())
	for j in range(q):
		k = int(input())
		if c == 'c3':
			ret.append(getCandies(data, s, k))
		elif c == 'c1':
			ret.append(getCandies4(data, k))
		elif c == 'c2':
			ret.append(getCandies2(data, k))
		elif ind is None and c == 'c4':
			ret.append(getCandies(data, s, k))
		else:
			ret.append(getCandies3(s, k, data, ind))
for i in ret:
	print(i % 1000000007)