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

Princess Rupsa saw one of her friends playing a special game. The game goes as follows:

N+1 numbers occur sequentially (one at a time) from A_{0} to A_{N}.
You must write the numbers on a sheet of paper, such that A_{0} is written first. The other numbers are written according to an inductive rule — after A_{i-1} numbers have been written in a row, then A_{i} can be written at either end of the row. That is, you first write A_{0}, and then A_{1} can be written on its left or right to make A_{0}A_{1} or A_{1}A_{0}, and so on.
A_{i} must be written before writing A_{j}, for every i < j.
For a move in which you write a number A_{i} (i>0), your points increase by the product of A_{i} and its neighbour. (Note that for any move it will have only one neighbour as you write the number at an end).
Total score of a game is the score you attain after placing all the N + 1 numbers.

Princess Rupsa wants to find out the sum of scores obtained by all possible different gameplays. Two gameplays are different, if after writing down all N + 1 numbers, when we read from left to right, there exists some position i, at which the gameplays have a_{j} and a_{k} written at the i^{th} position such that j ≠ k. But since she has recently found her true love, a frog Prince, and is in a hurry to meet him, you must help her solve the problem as fast as possible. Since the answer can be very large, print the answer modulo 10^{9} + 7.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.		
The first line of each test case contains a single integer N. 
The second line contains N + 1 space-separated integers denoting A_{0} to A_{N}.
 
------ Output ------ 

For each test case, output a single line containing an integer denoting the answer.

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

1 ≤ T ≤ 10
1 ≤ N ≤ 10^{5}
1 ≤ A_{i} ≤ 10^{9}

------ Sub tasks ------ 

Subtask #1: 1 ≤ N ≤ 10 (10 points)
Subtask #2: 1 ≤ N ≤ 1000 (20 points)
Subtask #3: Original Constraints (70 points)

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

1

1 2

2

1 2 1
----- Sample Output 1 ------ 
4

14
----- explanation 1 ------ 

There are 2 possible gameplays. A0A1 which gives score of 2 and  A1A0 which also gives score of 2. So the answer is 2 + 2 = 4

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Combinatorics

Mathematics

Ad-hoc

Starter code:

Solutions:
mod = 10 ** 9 + 7
for t in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	s = ans = 0
	for i in range(1, n + 1):
		s = (s + l[i - 1] % mod * max(2, pow(2, i - 1, mod))) % mod
		ans = (ans * 2 % mod + s * l[i] % mod) % mod
	print(ans)


for i in range(int(input())):
	m = 10 ** 9 + 7
	n = int(input())
	a = list(map(int, input().split()))
	t = 2 * a[0]
	x = 0
	p = 1
	for i in range(1, n + 1):
		p = 2 * p % m
		x = (2 * x + t * a[i]) % m
		t = (t + p * a[i]) % m
	print(x)


n = int(input())
for i in range(n):
	m = int(input())
	a = list(map(int, input().split()))
	b = 2 * a[0]
	sum = 0
	s = 1
	for j in range(1, m + 1):
		s = 2 * s % (10 ** 9 + 7)
		sum = (2 * sum + b * a[j]) % (10 ** 9 + 7)
		b = (b + s * a[j]) % (10 ** 9 + 7)
	print(sum)


t = int(input())
for _ in range(t):
	x = 1000000007
	n = int(input())
	l = list(map(int, input().split()))
	s = 2 * l[0]
	ans = 0
	c = 1
	for i in range(1, n + 1):
		c = 2 * c % x
		ans = (2 * ans + s * l[i]) % x
		s = (s + c * l[i]) % x
	print(ans)


mod = 10 ** 9 + 7

def rgame(a, n):
	s = 2 * a[0]
	ans = 0
	p = 1
	for i in range(1, n + 1):
		p = 2 * p % mod
		ans = (2 * ans + s * a[i]) % mod
		s = (s + p * a[i]) % mod
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(rgame(a, n))


for i in range(int(input())):
	s = 10 ** 9 + 7
	n = int(input())
	a = list(map(int, input().split()))
	t = 2 * a[0]
	ans = 0
	p = 1
	for i in range(1, n + 1):
		p = 2 * p % s
		ans = (2 * ans + t * a[i]) % s
		t = (t + p * a[i]) % s
	print(ans)


Mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	t = 2 * arr[0]
	result = 0
	p = 1
	for i in range(1, n + 1):
		p = 2 * p % Mod
		result = (2 * result + t * arr[i]) % Mod
		t = (t + p * arr[i]) % Mod
	print(result)


for i in range(int(input())):
	n = int(input())
	l = [int(d) for d in input().split()]
	r = 2 * l[0]
	c = 0
	a = 1
	for i in range(1, n + 1):
		a = 2 * a % (10 ** 9 + 7)
		c = (2 * c + r * l[i]) % (10 ** 9 + 7)
		r = (r + a * l[i]) % (10 ** 9 + 7)
	print(c)


def pow(n, pow, mod):
	if n == 0 or n == 1:
		return n % mod
	if pow == 0:
		return 1
	if mod == 1:
		return 0
	ans = 1
	while pow:
		if pow % 2:
			ans = ans * n % mod
		n = n * n % mod
		pow = pow / 2
mod = 10 ** 9 + 7
for i in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	v = 2 * arr[0]
	c = 0
	a = 1
	for i in range(1, n + 1):
		a = 2 * a % mod
		c = (2 * c + v * arr[i]) % mod
		v = (v + a * arr[i]) % mod
	print(c)


t = int(input())
for al in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = 2 * l[0]
	ans = 0
	a = 1
	for i in range(1, n + 1):
		a = 2 * a % (10 ** 9 + 7)
		ans = (2 * ans + x * l[i]) % (10 ** 9 + 7)
		x = (x + a * l[i]) % (10 ** 9 + 7)
	print(ans)


m = 10 ** 9 + 7
T = int(input())
for i in range(T):
	n = int(input())
	a = [int(x) for x in input().split()]
	t = 2 * a[0]
	ans = 0
	p = 1
	for i in range(1, n + 1):
		p = 2 * p % m
		ans = (2 * ans + t * a[i]) % m
		t = (t + p * a[i]) % m
	print(ans)


mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	temp = 2 * a[0]
	ans = 0
	p = 1
	for i in range(1, n + 1):
		p = 2 * p % mod
		ans = (2 * ans + temp * a[i]) % mod
		temp = (temp + p * a[i]) % mod
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(mul, mod) = ([a[0]], 1000000007)
	(sumy, temp) = (0, a[0])
	pr1 = 1
	for i in range(1, n + 1):
		pr = a[i] * temp
		sumy = 2 * sumy + pr
		temp += a[i] * pr1
		pr1 = pr1 * 2 % mod
	print(sumy * 2 % mod)


try:
	m = 10 ** 9 + 7

	def rg(l, n):
		r = 2 * l[0]
		sol = 0
		g = 1
		for i in range(1, n + 1):
			g = 2 * g % m
			sol = (2 * sol + r * l[i]) % m
			r = (r + g * l[i]) % m
		return sol
	for i in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		print(rg(l, n))
except:
	pass


mod = 10 ** 9 + 7
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	n += 1
	ans = 0
	l1 = [pow(2, i, mod) for i in range(n)]
	l1[0] = 2
	l2 = [l[i] * l1[i] % mod for i in range(n)]
	s = 0
	for i in range(1, n):
		s += l2[i - 1]
		s %= mod
		ans = (ans * 2 % mod + s * l[i] % mod) % mod
	print(ans % mod)


from sys import stdin
m = 10 ** 9 + 7
t = int(stdin.readline())
for e in range(t):
	n = int(stdin.readline()) + 1
	l = stdin.readline().split()
	(s, temp) = (0, 0)
	p = pow(2, n - 2, m)
	for i in range(n):
		l[i] = int(l[i])
	for j in range(1, n):
		pro = pow(2, n - j, m)
		s = s + pro * l[0] * l[j] % m
	for j in range(2, n):
		pro = pow(2, n - j, m)
		s = s + pro * l[1] * l[j] % m
		temp = temp + pro * l[j] % m
	for i in range(2, n):
		temp = 2 * (temp - l[i] * p) % m
		s = s + l[i] * temp % m
	print(s % m)


mod = 10 ** 9 + 7
n = int(input())
while n > 0:
	n -= 1
	x = int(input())
	lis = list(map(int, input().split()))
	(q, res) = (1, 0)
	c = lis[0]
	for i in range(1, x + 1):
		res = (2 * res + c * lis[i] * 2) % mod
		c = (c + q * lis[i]) % mod
		q = 2 * q % mod
	print(res)


for tc in range(int(input())):
	n = int(input())
	mod = 10 ** 9 + 7
	lst = [int(x) for x in input().split()]
	v = 2 * lst[0]
	c = 0
	a = 1
	for i in range(1, n + 1):
		a = 2 * a % mod
		c = (2 * c + v * lst[i]) % mod
		v = (v + a * lst[i]) % mod
	print(c)


M = 10 ** 9 + 7
for t in range(int(input())):
	N = int(input())
	L = [int(i) for i in input().split()]
	A = res = 0
	for i in range(1, N + 1):
		A = (A + L[i - 1] % M * max(2, pow(2, i - 1, M))) % M
		res = (res * 2 % M + A * L[i] % M) % M
	print(res)


t = int(input())
for i in range(t):
	s = 10 ** 9 + 7
	n = int(input())
	l = list(map(int, input().split()))
	c = 2 * l[0]
	ans = 0
	p = 1
	for j in range(1, n + 1):
		p = 2 * p % s
		ans = (2 * ans + c * l[j]) % s
		c = (c + p * l[j]) % s
	print(ans)


mod = 10 ** 9 + 7

def solve(l, n):
	s = 2 * l[0]
	ans = 0
	p = 1
	for i in range(1, n + 1):
		p = 2 * p % mod
		ans = (2 * ans + s * l[i]) % mod
		s = (s + p * l[i]) % mod
	return int(ans)
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	print(solve(l, n))


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(j) for j in input().split()]
	x = 2 * a[0]
	c = 0
	y = 1
	for i in range(1, n + 1):
		y = 2 * y % (10 ** 9 + 7)
		c = (2 * c + x * a[i]) % (10 ** 9 + 7)
		x = (x + y * a[i]) % (10 ** 9 + 7)
	print(c)


M = 1000000007
for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	n1 = a[0]
	S = 0
	E = 2 * n1
	m = 2
	for i in range(1, N + 1):
		S = (2 * S + E * a[i]) % M
		E = (E + m * a[i]) % M
		m = 2 * m % M
	print(S)


def cal(l, n1):
	a = 2 * l[0]
	r = 0
	p = 1
	for i in range(1, n1 + 1):
		p = 2 * p % (10 ** 9 + 7)
		r = (2 * r + a * l[i]) % (10 ** 9 + 7)
		a = (a + p * l[i]) % (10 ** 9 + 7)
	return int(r)
n = int(input())
for i in range(n):
	a = int(input())
	l = list(map(int, input().split()))
	print(cal(l, a))


try:
	t = int(input())
	m = 10 ** 9 + 7
	for test in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		q = a[0]
		p = 1
		s = 0
		for i in range(1, n + 1):
			s = (2 * s + 2 * q * a[i]) % m
			q += p * a[i] % m
			p = 2 * p % m
		print(s)
except:
	pass


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	c = 2 * A[0]
	p = 1
	s = 10 ** 9 + 7
	for i in range(1, N + 1):
		p = 2 * p % s
		ans = (2 * ans + c * A[i]) % s
		c = (c + p * A[i]) % s
	print(ans)


m = 10 ** 9 + 7
for j in range(int(input())):
	num_tests = int(input())
	a = list(map(int, input().split()))
	temp = 2 * a[0]
	ans = 0
	p = 1
	for i in range(1, num_tests + 1):
		p = 2 * p % m
		ans = (2 * ans + temp * a[i]) % m
		temp = (temp + p * a[i]) % m
	print(ans)


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 2 * a[0]
	res = 0
	x = 1
	for i in range(1, n + 1):
		x = 2 * x % MOD
		res = (2 * res + s * a[i]) % MOD
		s = (s + x * a[i]) % MOD
	print(res)


m = 1000000000 + 7
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 2 * a[0]
	ans = 0
	p = 1
	for i in range(1, n + 1):
		p = 2 * p % m
		ans = (2 * ans + s * a[i]) % m
		s = (s + p * a[i]) % m
	print(ans)


tc = int(input())
for _ in range(tc):
	X = 1000000007
	n = int(input())
	li = list(map(int, input().split()))
	s = 2 * li[0]
	ans = 0
	o = 1
	for i in range(1, n + 1):
		o = 2 * o % X
		ans = (2 * ans + s * li[i]) % X
		s = (s + o * li[i]) % X
	print(ans)


t = int(input())
for _ in range(t):
	x = 1000000007
	n = int(input())
	l = list(map(int, input().split()))
	sq = 2 * l[0]
	ans = 0
	count = 1
	for i in range(1, n + 1):
		count = 2 * count % x
		ans = (2 * ans + sq * l[i]) % x
		sq = (sq + count * l[i]) % x
	print(ans)


mod = 10 ** 9 + 7
T = int(input())
for i in range(T):
	N = int(input())
	a = [int(x) for x in input().split()]
	t = 2 * a[0]
	answer = 0
	p = 1
	for i in range(1, N + 1):
		p = 2 * p % mod
		answer = (2 * answer + t * a[i]) % mod
		t = (t + p * a[i]) % mod
	print(answer)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	sz = int(input())
	ar = list(map(int, input().split()))
	s = 2 * ar[0]
	ans = 0
	pro = 1
	for i in range(1, sz + 1):
		pro = pro * 2 % mod
		ans = (s * ar[i] + ans * 2) % mod
		s = (pro * ar[i] + s) % mod
	print(ans)


m = 10 ** 9 + 7
t = int(input())
for e in range(t):
	n = int(input()) + 1
	l = input().split()
	(s, temp) = (0, 0)
	p = pow(2, n - 2, m)
	for i in range(n):
		l[i] = int(l[i])
	for j in range(1, n):
		pro = pow(2, n - j, m)
		s = s + pro * l[0] * l[j] % m
	for j in range(2, n):
		pro = pow(2, n - j, m)
		s = s + pro * l[1] * l[j] % m
		temp = temp + pro * l[j] % m
	for i in range(2, n):
		temp = 2 * (temp - l[i] * p) % m
		s = s + l[i] * temp % m
	print(s % m)