Consider an array, $\mbox{A}$, of length $n$. We can split $\mbox{A}$ into contiguous segments called pieces and store them as another array, $\mbox{B}$. For example, if $A=[1,2,3]$, we have the following arrays of pieces:

$B=[(1),(2),(3)]$ contains three $\mbox{1}$-element pieces.
$B=[(1,2),(3)]$ contains two pieces, one having $2$ elements and the other having $\mbox{1}$ element.
$B=[(1),(2,3)]$ contains two pieces, one having $\mbox{1}$ element and the other having $2$ elements.
$B=[(1,2,3)]$ contains one $3$-element piece.

We consider the value of a piece in some array $\mbox{B}$ to be $\textit{(sum of all numbers in the piece)}\times\textit{(length of piece)}$, and we consider the total value of some array $\mbox{B}$ to be the sum of the values for all pieces in that $\mbox{B}$. For example, the total value of $B=[(1,2,4),(5,1),(2)]$ is $(1+2+4)\times3+(5+1)\times2+(2)\times1=35$.

Given $\mbox{A}$, find the total values for all possible $\mbox{B}$'s, sum them together, and print this sum modulo $(10^9+7)$ on a new line.

Input Format

The first line contains a single integer, $n$, denoting the size of array $\mbox{A}$. 

The second line contains $n$ space-separated integers describing the respective values in $\mbox{A}$ (i.e., $a_0,a_1,\ldots,a_{n-1}$).

Constraints

$1\leq n\leq10^{6}$
$1\leq a_i\leq10^9$

Output Format

Print a single integer denoting the sum of the total values for all piece arrays ($\mbox{B}$'s) of $\mbox{A}$, modulo $(10^9+7)$.

Sample Input 0

3
1 3 6

Sample Output 0

73

Explanation 0 

Given $A=[1,3,6]$, our piece arrays are:

$B=[(1),(3),(6)]$, and $total value=(1)\times1+(3)\times1+(6)\times1=10$.
$B=[(1,3),(6)]$, and $total value=(1+3)\times2+(6)\times1=14$.
$B=[(1),(3,6)]$, and $total value=(1)\times1+(3+6)\times2=19$.
$B=[(1,3,6)]$, and $total value=(1+3+6)\times3=30$.

When we sum all the total values, we get $10+14+19+30=73$. Thus, we print the result of $73\ \text{mod}\ (10^9+7)=73$ on a new line.

Sample Input 1

5
4 2 9 10 1

Sample Output 1

971

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
def coeff(n):
	a = pow(2, n, 1000000007)
	res = [a - 1]
	for i in range((n - 1) // 2):
		a = a * 250000002 % 1000000007
		res.append((res[-1] + (a - 1) * pow(2, i, 1000000007)) % 1000000007)
	if n & 1:
		return res + res[-2::-1]
	return res + res[::-1]
print(sum(map(lambda x, y: x * y % 1000000007, coeff(int(input())), map(int, input().split()))) % 1000000007)


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

def ri():
	return int(input())

def powmod(x, power, mod):
	if power == 0:
		return 1
	mult = 1
	while power != 1:
		if power & 1:
			mult = mult * x % mod
		x = x * x % mod
		power //= 2
	return x * mult % mod

def main():
	n = ri()
	arr = r()
	mod = 10 ** 9 + 7
	ans = 0
	addend = powmod(2, n, mod) + powmod(2, n - 1, mod)
	for (i, x) in enumerate(arr):
		if i == 0:
			two_pow_i = 1
		else:
			two_pow_i = two_pow_i * 2 % mod
		two_pow_n_minus_i_minus_one = powmod(2, n - i - 1, mod)
		ans += x * (addend - two_pow_i - two_pow_n_minus_i_minus_one)
	print(ans % mod)
main()


n = int(input().strip())
p = [0 for i in range(n + 1)]
pk = 1
for i in range(n + 1):
	p[i] = pk - 1
	pk = 2 * pk % (10 ** 9 + 7)
a = list(map(int, input().strip().split()))
factor = p[n]
total = p[n] * a[0]
for i in range(1, n):
	factor = (factor + p[n - i - 1] - p[i - 1]) % (10 ** 9 + 7)
	total = (total + a[i] * factor) % (10 ** 9 + 7)
print(total % (10 ** 9 + 7))


n = eval(input())
a = [int(x) for x in input().split()]
mod = 10 ** 9 + 7
powers = [1]
p = 1
for i in range(n):
	p <<= 1
	p %= mod
	powers.append(p)
total = 0
mid = -1 if n % 2 == 0 else n // 2
coef = 0
for i in range((n + 1) // 2):
	base = a[i] + a[-i - 1] if i != mid else a[i]
	coef += powers[n if i == 0 else n - i - 1] - powers[max(0, i - 1)]
	coef %= mod
	total += coef * base
	total %= mod
print(total)


MOD = 1000000007
n = int(input())
A = [int(x) for x in input().split()]
table = dict()
power = 1
table[0] = 1
for exponent in range(1, n - 1):
	power = 2 * power % MOD
	table[exponent] = power

def waysofsplitting(i, j):
	exponent = n - (j - i) - 2
	if i == 0:
		exponent += 1
	if j == n:
		exponent += 1
	return table[exponent]
psums = dict()
total = 0
psums[0] = 0
for i in range(n):
	total = (total + A[i]) % MOD
	psums[i + 1] = total

def psumi(i, j):
	return (psums[j] - psums[i]) % MOD
ladder = dict()
ladder[0] = 0
temp = 0
for i in range(1, n // 2 + 1):
	temp = (temp + psumi(i, n - i)) % MOD
	ladder[i] = temp
result = 0
for k in range(1, n + 1):
	if k == n:
		result = (result + psumi(0, n) * n) % MOD
		continue
	if k <= n - k:
		temp = psumi(k, n - k) % MOD
	else:
		temp = 0
	ladder_height = min(k, n - k)
	temp = (temp + ladder[ladder_height - 1]) % MOD
	temp = temp * k % MOD
	temp = temp * waysofsplitting(1, 1 + k) % MOD
	temp2 = (psumi(0, k) + psumi(n - k, n)) * k % MOD
	temp2 = temp2 * waysofsplitting(0, k) % MOD
	result = (result + temp + temp2) % MOD
print(result)


mod = 10 ** 9 + 7
n = int(input())
A = list(map(int, input().split()))
total = 0
for z in range(n // 2 + (n % 2 != 0)):
	if z == 0:
		weight = (pow(2, n, mod) - 1) % mod
		i = n - 1
		j = 0
	else:
		weight += pow(2, i, mod) - pow(2, i - 1, mod) - pow(2, j, mod)
		weight %= mod
		i -= 1
		j += 1
	total += A[z] * weight % mod
	if n % 2 != 0 and z >= n // 2:
		break
	total += A[-(z + 1)] * weight % mod
print(total % mod)


import sys
n = int(sys.stdin.readline())
x = list(map(int, sys.stdin.readline().split()))
a = 1
for i in range(0, n):
	a = a * 2 % 1000000007
a = (a - 1) % 1000000007
b2 = [0]
b = 1
for i in range(0, n - 1):
	b2.append(b)
	b = b * 2 % 1000000007
c = 1
sol = 0
for i in range(0, n):
	if i != 0:
		a += (b2[n - i] - c) % 1000000007
		c *= 2
		c %= 1000000007
	sol = (sol + x[i] * a) % 1000000007
print(sol)


from math import ceil
N = int(input())
nums = [int(n) for n in input().split()]
total = 0
powa = pow(2, N, 1000000007) - 1
if N > 1:
	total += powa * (nums[0] % 1000000007 + nums[-1] % 1000000007)
else:
	total = nums[0]
M = N - 2
for n in range(N // 2 - 1):
	powa += pow(2, M, 1000000007) - pow(2, n, 1000000007)
	M -= 1
	total += powa * (nums[1 + n] % 1000000007 + nums[N - 2 - n] % 1000000007) % 1000000007
if N % 2 == 1 and N > 1:
	powa += pow(2, M, 1000000007) - pow(2, ceil(N / 2) - 2, 1000000007)
	total += powa * nums[N // 2] % 1000000007
print(total % 1000000007)


MOD = 10 ** 9 + 7

def sumpieces(arr):
	pow2 = 1
	value = 0
	sumlast = 0
	for elt in arr:
		value = (2 * value + sumlast + (2 * pow2 - 1) * elt) % MOD
		sumlast = (sumlast + pow2 * elt) % MOD
		pow2 = 2 * pow2 % MOD
	return value
n = int(input())
arr = [int(fld) for fld in input().strip().split()]
print(sumpieces(arr))


M = 1000000007
n = int(input())
a = list(map(int, input().split()))
(p2, invp2) = ([1], [1])
for _ in range(n + 2):
	p2.append(p2[-1] * 2 % M)
	invp2.append(invp2[-1] * (M + 1) // 2 % M)

def c(k):
	if k > (n + 1) // 2:
		k = n - k + 1
	if k == 1:
		return (p2[n] - 1) % M
	r = (k + 1) * p2[n - k] - 1
	r += ((p2[k] - 2) * n + 2 * (p2[k] - 1) - k * p2[k]) * invp2[1]
	r += invp2[k + 1] * ((p2[n] - p2[k]) * (3 * p2[k] - 4) + k * (p2[k] * p2[k] - p2[n + 1]) - p2[k] * (p2[k] - 2) * n)
	return r % M
print(sum([c(i) * a[i - 1] % M for i in range(1, n + 1)]) % M)


def f(x, y):
	return (x + y) * (y - x + 1) // 2
MOD = 1000000007
n = int(input())
a = [int(x) for x in input().split()]
pow2 = [1] * (n + 1)
for i in range(1, n + 1):
	pow2[i] = pow2[i - 1] * 2 % MOD
delta = 0
for i in range(n - 2):
	delta += pow2[i]
	delta %= MOD
(st, ed) = (0, n - 3)
result = 0
base = pow2[n] - 1
for i in range((n + 1) // 2):
	if i == n - 1 - i:
		tar = a[i]
	else:
		tar = (a[i] + a[n - 1 - i]) % MOD
	result += base * tar % MOD
	result %= MOD
	base = (base + delta) % MOD
	delta = delta - pow2[st] - pow2[ed]
	st += 1
	ed -= 1
	while delta < 0:
		delta += MOD
print(result)


def trace(a, current_a, current_sum, start, end):
	if start == len(a):
		yield current_a
	for i in range(start + 1, end + 1):
		yield from trace(a, current_a + [a[start:i]], current_sum + sum(a[start:i]) * (i - start), i, end)

def print_patterns():
	for n in range(2, 11):
		a = [i for i in range(n)]
		patterns = [0 for _ in range(n)]
		for current_a in trace(a, [], 0, 0, len(a)):
			for group in current_a:
				for number in group:
					patterns[number] += len(group)
		print(patterns)

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number

def generate_pattern(n):
	if n == 1:
		return [1]
	pattern = [None for i in range(n)]
	pattern[0] = (pow_mod(2, n, 1000000007) - 1) % 1000000007
	for i in range(1, (n - 1) // 2 + 1):
		pattern[i] = (pattern[i - 1] % 1000000007 + pow_mod(2, n - i - 1, 1000000007) - pow_mod(2, i - 1, 1000000007)) % 1000000007
	for i in range(n // 2, n):
		pattern[i] = pattern[n - i - 1]
	return pattern
n = int(input())
a = [int(number) for number in input().strip().split(' ')]
pattern = generate_pattern(n)
total_sum = 0
for i in range(n):
	total_sum += a[i] % 1000000007 * pattern[i] % 1000000007 % 1000000007
print(total_sum % 1000000007)


import math
n = int(input())
A = list(map(int, input().split()))
T = [0] * n
MOD = 10 ** 9 + 7

def pow_mod(x, y):
	number = 1
	while y:
		if y & 1:
			number = number * x % MOD
		y >>= 1
		x = x * x % MOD
	return number
mem = pow_mod(2, n) + pow_mod(2, n - 1)
ans = 0
k = 0
for i in range(1, math.ceil(n / 2) + 1):
	temp = mem - pow_mod(2, n - i) - pow_mod(2, i - 1)
	T[i - 1] = temp
	T[n - i] = temp
for a in A:
	ans = (ans + T[k] * a) % MOD
	k += 1
print(ans)


n = int(input())
a = input().split()
res = 0
m = 10 ** 9 + 7

def f(e):
	X = 2
	E = e
	Y = 1
	while E > 0:
		if E % 2 == 0:
			X = X * X % m
			E = E / 2
		else:
			Y = X * Y % m
			E = E - 1
	return Y
f1 = f(n)
f2 = f(n - 1)
l = [pow(2, k, m) for k in range(0, n)]
for k in range(1, n + 1):
	res += (f1 + f2 - l[n - k] - l[k - 1]) * int(a[k - 1])
print(res % (10 ** 9 + 7))


m = 10 ** 9 + 7
n = int(input())
arr = map(int, input().split())
mult = pow(2, n, m) - 1
total = mult * next(arr)
for i in range(1, n):
	mult = (mult + pow(2, n - i - 1, m) - pow(2, i - 1, m)) % m
	total = (total + mult * next(arr)) % m
print(total)


mod = 10 ** 9 + 7
n = int(input())
A = list(map(int, input().split()))
A = [0] + A
E = []
v = 0
for i in A:
	v = (v + i) % mod
	E.append(v)
S = [1, 1]
for i in range(1, n + 1):
	S.append(S[i] * 2 % mod)
P = [0]
T = [0]
for i in range(1, n + 1):
	P.append((P[i - 1] + E[i] * S[i]) % mod)
	T.append(T[i - 1] + P[i])
res = [0]
total = [0]
for i in range(1, n + 1):
	LHS = total[i - 1]
	RHS = (E[i] * (2 * S[i] - 1) - T[i - 1]) % mod
	res.append((LHS + RHS) % mod)
	total.append((total[i - 1] + res[i]) % mod)
print(res[n] % mod)


def encode(i, n):
	i = i - 1
	if i > (n - 1) // 2:
		return encode(n - i, n)
	if i == 0 or i == n - 1:
		X = ['0'] + ['1'] * n
	else:
		X = ['1'] * (n + 1)
		for k in range(0, n + 1):
			if k == 1 or k == i + 1 or n - k < i:
				X[k] = '0'
	return ''.join(X)

def encode2(i, n):
	p = 10 ** 9 + 7
	i = i - 1
	if i > (n - 1) // 2:
		return encode2(n - i, n)
	if i == 0:
		return pow(2, n, p) - 1
	return (pow(2, n + 1, p) - pow(2, n - 1, p) - pow(2, n - i - 1, p) - pow(2, i, p)) % p

def counts(n):
	count = [0 for i in range(0, n)]
	for i in range(0, 2 ** (n - 1)):
		X = format(i, '0' + str(n - 1) + 'b') + '1'
		X = ''.join(['0' for x in range(0, len(X) - n)]) + X
		print('i', i)
		print('X', X)
		add = [0] * n
		for j in range(0, n):
			print(j, n)
			toRight = next((k for k in range(j, n) if X[k] == '1'))
			toLeft = next((k for k in reversed(range(0, j)) if X[k] == '1'), -1)
			print('j toRight toLeft', j, toRight, toLeft, toRight - toLeft)
			add[j] = toRight - toLeft
		print(add)
		count = [count[j] + add[j] for j in range(0, n)]
	return count

def comp(X):
	s = 0
	for i in range(0, len(X)):
		if X[len(X) - 1 - i] == '1':
			s = s + pow(2, i, 10 ** 9 + 7) % (10 ** 9 + 7)
	return s
n = int(input())
A = list(map(int, input().split()))
s = 0
for i in range(0, n // 2):
	s = s + (A[i] + A[n - 1 - i]) * encode2(i + 1, n) % (10 ** 9 + 7)
if n % 2 == 1:
	s = s + A[n // 2] * encode2(n // 2 + 1, n) % (10 ** 9 + 7)
s = (s + 10 ** 9 + 7) % (10 ** 9 + 7)
print(s)


n = int(input())
a = list(map(int, input().split()))
r = 0
M = 10 ** 9 + 7

def get_mul(k, j):
	return pow(2, j, M) * (pow(2, k - j, M) - 1) + pow(2, k - j, M) * (pow(2, j + 1, M) - 1)
for (j, x) in enumerate(a):
	r = (r + get_mul(n - 1, j) * x) % M
print(r)


n = int(input())
arr = [int(i) for i in input().split()]
mod = 1000000007
powerof2 = [0] * 1000001
powerof2[0] = 1
for i in range(1, 1000001):
	powerof2[i] = powerof2[i - 1] * 2 % mod
ans = 0
for i in range(0, n):
	power = (powerof2[n] + powerof2[n - 1] - powerof2[n - (i + 1)] - powerof2[i]) % mod
	ans = (ans + arr[i] * power % mod) % mod
print(ans)


import math
M = 10 ** 9 + 7
n = int(input())
powers_mod = [1]
for i in range(n):
	powers_mod.append(powers_mod[-1] * 2 % M)
arr = list(map(int, input().split()))
multiplier = powers_mod[n] - 1
last_diff = powers_mod[n - 2] - 1
total = 0
for i in range(math.ceil(n / 2)):
	total += arr[i] * multiplier % M
	if n % 2 != 1 or i != n // 2:
		total += arr[n - i - 1] * multiplier
	multiplier = (multiplier + last_diff) % M
	last_diff = (last_diff - powers_mod[n - i - 3] - powers_mod[i]) % M
print(total % M)


n = int(input())
no = [int(x) for x in input().split()]
power = [1]
mod = 10 ** 9 + 7
for i in range(1, n):
	power.append(((power[i - 1] + 1 << 1) - 1) % mod)
first = 0
mul = []
if n % 2 == 1:
	first = 1
s = 0
j = 0
for i in range(0, int(n / 2) + first):
	if i == 0:
		mul.append((power[n - 2] * 2 + power[0]) % mod)
	else:
		mul.append((power[n - 2 - i] * ((2 + power[i - 1] * 3) % mod) + power[i]) % mod)
	s = (s + mul[i] * no[i] % mod) % mod
	j += 1
for i in range(int(n / 2) - 1, -1, -1):
	s = (s + mul[i] * no[j] % mod) % mod
	j += 1
print(s)


def modular_exp(x, number):
	res = 1
	while number > 0:
		if number % 2 == 1:
			res = res * x % (10 ** 9 + 7)
		number = number // 2
		x = x * x % (10 ** 9 + 7)
	return res
n = int(input())
array = list((int(x) for x in input().split()))
answer = 0
x = 0
if n % 2 == 0:
	multiplier = modular_exp(2, n) - 1
	while x < n // 2:
		current_number = array[x] + array[-x - 1]
		answer = (answer + current_number * multiplier) % (10 ** 9 + 7)
		multiplier = multiplier + (modular_exp(2, n - 2 - x) - modular_exp(2, x))
		x += 1
else:
	multiplier = modular_exp(2, n) - 1
	while x < n // 2:
		current_number = array[x] + array[-x - 1]
		answer = (answer + current_number * multiplier) % (10 ** 9 + 7)
		multiplier = multiplier + (modular_exp(2, n - 2 - x) - modular_exp(2, x))
		x += 1
	answer = (answer + array[n // 2] * multiplier) % (10 ** 9 + 7)
print(answer % (10 ** 9 + 7))


def fast_power(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
m = 1000000007
n = int(input())
arr = list(map(int, input().split()))
n += 1
pre = [0 for i in range(n)]
pre[0] = (fast_power(2, n - 1, m) % m - 1 % m + m) % m
if n % 2 == 0:
	k = n - 3
	j = 0
	for i in range(1, n // 2):
		pre[i] = (pre[i - 1] % m + fast_power(2, k, m) % m) % m
		pre[i] = (pre[i] % m - fast_power(2, j, m) % m + m) % m
		k -= 1
		j += 1
	j = n // 2 - 2
	for i in range(n // 2, n):
		pre[i] = pre[j]
		j -= 1
	ans = 0
	for i in range(n - 1):
		ans = (ans % m + arr[i] % m * pre[i] % m % m) % m
	print(ans)
else:
	k = n - 3
	j = 0
	for i in range(1, n // 2 + 1):
		pre[i] = (pre[i - 1] % m + fast_power(2, k, m) % m) % m
		pre[i] = (pre[i] % m - fast_power(2, j, m) % m + m) % m
		k -= 1
		j += 1
	j = i - 1
	while i < n:
		pre[i] = pre[j]
		i += 1
		j -= 1
	ans = 0
	for i in range(n - 1):
		ans = (ans % m + arr[i] % m * pre[i] % m % m) % m
	print(ans)


data = [1, 3, 6]
data = [4, 2, 9, 10, 1]
n = int(input())
data = [int(x) for x in input().split()]
answer = 0
ptcache = []

def fast_exp(n):
	if n == 0:
		return 1
	if n == 1:
		return 2
	if n % 2 == 0:
		cv = fast_exp(n // 2)
		return cv * cv
	else:
		cv = fast_exp(n // 2)
		return 2 * cv * cv
powoftwo = 1
for i in range(n + 1):
	ptcache.append(powoftwo)
	powoftwo = 2 * powoftwo % 1000000007
c1 = ptcache[n - 1]
c = c1 * 3
c2 = 1 << 1 - 1
for (i, x) in enumerate(data, 1):
	xxxx = c - ptcache[n - i] - ptcache[i - 1]
	xxx = x * xxxx % 1000000007
	answer += xxx % 1000000007
print(answer % 1000000007)


n = int(input())
a = list(map(int, input().strip().split()))
m = 1000000007
pow2 = [1] * (n + 1)
for i in range(1, n + 1):
	pow2[i] = pow2[i - 1] * 2 % m
coeff = [-1] * n
coeff[0] = (pow2[n] - 1) % m
for i in range(1, n):
	coeff[i] = (coeff[i - 1] + pow2[n - i - 1] - pow2[i - 1]) % m
ans = 0
for i in range(n):
	ans = (ans % m + coeff[i] * a[i] % m) % m
print(ans)


pp = int(input())
arr = [int(i) for i in input().split()]
mod = 1000000007
pow2 = [0] * 1000001
pow2[0] = 1
for i in range(1, 1000001):
	pow2[i] = pow2[i - 1] * 2 % mod
sum = 0
for i in range(0, pp):
	pow = (pow2[pp] + pow2[pp - 1] - pow2[pp - (i + 1)] - pow2[i]) % mod
	sum = (sum + arr[i] * pow % mod) % mod
print(sum)


import math
tp = {0: 1}

def getTP(n):
	for i in range(n + 1):
		if i - 1 in tp:
			k = 2 * tp[i - 1] % (10 ** 9 + 7)
			tp[i] = k
		else:
			k = 2 ** i % (10 ** 9 + 7)
			tp[i - 1] = k / 2

def getNum(n):
	powers = [tp[n] - 1]
	k = math.ceil((n - 2) / 2)
	for i in range(k):
		powers.append((powers[i] + tp[n - 2 - i] - tp[i]) % (10 ** 9 + 7))
	if n % 2 == 1:
		temp = list(powers)
		temp.remove(temp[k])
		powers = powers + temp[::-1]
	else:
		powers = powers + powers[::-1]
	return powers
n = int(input())
l = [int(x) for x in input().split()]
getTP(n)
if n != 1:
	powers = getNum(n)
	t = 0
	for i in range(n):
		t += l[i] * powers[i]
		t = t % (10 ** 9 + 7)
	print(int(t))
else:
	print(l[0])


n = int(input())
arr = [int(x) for x in input().split()]
muls = []
mod = 10 ** 9 + 7
base = pow(2, n, mod) - 1
initial = n - 2
correction = 1
count = base * arr[0] + base * arr[n - 1]
two_pow = 1
if n == 1:
	print(arr[0])
elif n % 2 != 0:
	for i in range(1, n // 2 + 1):
		base += pow(2, initial, mod) - correction
		muls.append(base)
		count += base * arr[i]
		initial -= 1
		correction = pow(2, two_pow, mod)
		two_pow += 1
	j = len(muls) - 2
	for i in range(n // 2 + 1, n - 1):
		count += muls[j] * arr[i]
		j -= 1
	print(count % mod)
else:
	for i in range(1, n // 2):
		base += pow(2, initial, mod) - correction
		muls.append(base)
		count += base * arr[i]
		initial -= 1
		correction = pow(2, two_pow, mod)
		two_pow += 1
	j = len(muls) - 1
	for i in range(n // 2, n - 1):
		count += muls[j] * arr[i]
		j -= 1
	print(count % mod)


n = int(input())
l = [int(x) for x in input().split()]
total = 0
mod = 10 ** 9 + 7
store = pow(2, n, mod) - 1
for x in range(0, n // 2):
	total += (l[x] + l[-x - 1]) % mod * store % mod
	store += (pow(2, n - 2 - x, mod) - pow(2, x, mod)) % mod
if n % 2 == 1:
	total += l[n // 2] * store
print(total % mod)


mod = 1000000007
n = int(input())
a = [int(i) for i in input().split()]
mod_inverse = pow(2, mod - 2, mod)
high = pow(2, n, mod)
low = 1
if n == 1:
	print(a[0])
elif n == 2:
	print((a[0] + a[1]) * 3 % mod)
elif n % 2 == 0:
	ans = (high - 1) * a[0] % mod
	ans += (high - 1) * a[n - 1] % mod
	temp = (high - 1) % mod
	high = high * mod_inverse % mod
	high = high * mod_inverse % mod
	for i in range(1, n // 2):
		ans += (temp + high - low) * a[i]
		ans = ans % mod
		ans += (temp + high - low) * a[n - 1 - i]
		ans = ans % mod
		temp += (high - low) % mod
		high = high * mod_inverse % mod
		low = low * 2 % mod
	print(ans)
else:
	ans = (high - 1) * a[0] % mod
	ans += (high - 1) * a[n - 1] % mod
	temp = (high - 1) % mod
	high = high * mod_inverse % mod
	high = high * mod_inverse % mod
	for i in range(1, n // 2):
		ans += (temp + high - low) * a[i]
		ans = ans % mod
		ans += (temp + high - low) * a[n - 1 - i]
		ans = ans % mod
		temp += (high - low) % mod
		high = high * mod_inverse % mod
		low = low * 2 % mod
	ans += (temp + high - low) * a[n // 2]
	ans = ans % mod
	print(ans)


n = int(input())
a = list(map(int, input().split(' ')))
result = a[0]
result_sum = result
sum_t = a[0]
sum_2 = sum_t
x1 = sum_t
for i in range(1, n):
	sum_t = (sum_t + a[i]) % 1000000007
	result = (result_sum + (pow(2, i + 1, 1000000007) - 1) * sum_t - x1) % 1000000007
	result_sum = (result_sum + result) % 1000000007
	x1 = (x1 + pow(2, i, 1000000007) * sum_t + sum_2) % 1000000007
	sum_2 = (sum_2 + pow(2, i, 1000000007) * sum_t) % 1000000007
print(result % (10 ** 9 + 7))


import sys
N = int(input())
A = [int(i) for i in input().strip().split()]
total = 0
adder = 0
power = 1
increment = 0
for a in range(len(A)):
	adder += power % 1000000007
	lastrow = adder * A[a]
	total = (2 * total + adder * A[a] + increment) % 1000000007
	increment = (increment + power * A[a]) % 1000000007
	power = power * 2 % 1000000007
print(total % 1000000007)


n = int(input())
arr = [int(x) for x in input().split()]
muls = []
mod = 10 ** 9 + 7
base = pow(2, n, mod) - 1
initial = n - 2
correction = 1
count = base * arr[0] + base * arr[n - 1]
two_pow = 1
if n == 1:
	print(arr[0])
elif n % 2 != 0:
	for i in range(1, n // 2 + 1):
		base += pow(2, initial, mod) - correction
		muls.append(base)
		count += base * arr[i]
		initial -= 1
		correction = pow(2, two_pow, mod)
		two_pow += 1
	j = len(muls) - 2
	for i in range(n // 2 + 1, n - 1):
		count += muls[j] * arr[i]
		j -= 1
	print(count % mod)
else:
	for i in range(1, n // 2):
		base += pow(2, initial, mod) - correction
		muls.append(base)
		count += base * arr[i]
		initial -= 1
		correction = pow(2, two_pow, mod)
		two_pow += 1
	j = len(muls) - 1
	for i in range(n // 2, n - 1):
		count += muls[j] * arr[i]
		j -= 1
	print(count % mod)


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


n = int(input())
no = [int(x) for x in input().split()]
(power, mod, first, mul, s, j) = ([1], 10 ** 9 + 7, 0, [], 0, 0)
for i in range(1, n):
	power.append(((power[i - 1] + 1 << 1) - 1) % mod)
if n % 2 == 1:
	first = 1
for i in range(0, int(n / 2) + first):
	if i == 0:
		mul.append((power[n - 2] * 2 + power[0]) % mod)
	else:
		mul.append((power[n - 2 - i] * (2 + power[i - 1] * 3) % mod + power[i]) % mod)
	s = (s + mul[i] * no[i] % mod) % mod
	j += 1
for i in range(int(n / 2) - 1, -1, -1):
	s = (s + mul[i] * no[j] % mod) % mod
	j += 1
print(s)


import sys
import random
n = int(input().strip())
d = list(map(int, input().strip().split(' ')))
a = []
for x in range(n):
	a.append(pow(2, x, 1000000007))
l = []
s = pow(2, n, 1000000007)
if s > 0:
	s -= 1
l.append(s)
m = (n - 1) // 2
x = l[0]
c = 0
s = n - 2
while c < m:
	tmp = (a[s - c] - a[c]) % 1000000007
	if tmp < 0:
		tmp += 1000000007
	x += tmp
	x = x % 1000000007
	l.append(x)
	c += 1
s = 0
m += 1
for x in range(n):
	if x < m:
		s += l[x] * d[x] % 1000000007
	else:
		s += l[n - x - 1] * d[x] % 1000000007
	s = s % 1000000007
print(s)


def fast_exp_mod(a, b, p):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % p
		a = a * a % p
		b = b >> 1
	return res
n = int(input())
a = []
mult = []
s = str(input())
s = s.split()
for i in range(n):
	a.append(int(s[i]))
	mult.append(0)
if n % 2 == 0:
	even = True
	mid = int(n / 2 - 1)
else:
	even = False
	mid = int(n / 2)
y = n - 2
k = 0
mult[0] = (2 ** n - 1) % (10 ** 9 + 7)
mult[n - 1] = mult[0]
j = n - 2
sumall = 0
for i in range(1, mid + 1):
	if i == mid and even == False:
		mult[i] = (mult[i - 1] % 1000000007 + (fast_exp_mod(2, y, 1000000007) - fast_exp_mod(2, k, 1000000007)) % 1000000007) % 1000000007
		break
	mult[i] = (mult[i - 1] % 1000000007 + (fast_exp_mod(2, y, 1000000007) - fast_exp_mod(2, k, 1000000007)) % 1000000007) % 1000000007
	mult[j] = mult[i]
	j -= 1
	k += 1
	y -= 1
for i in range(n):
	sumall = (sumall + a[i] * mult[i] % 1000000007) % 1000000007
print(sumall)


m = 10 ** 9 + 7

def size_of_piece(L):
	return sum(L) * len(L)
n = int(input())
A = [int(x) for x in input().split()]
P = [0] * n
tot = 0
for i in range(n):
	if i == 0:
		P[i] = (2 ** n - 1) % m
	elif i < n / 2:
		P[i] = (P[i - 1] + pow(2, n - 1 - i, m) - pow(2, i - 1, m)) % m
	else:
		P[i] = P[n - 1 - i]
	tot += P[i] * A[i] % m
print(tot % m)


n = int(input())
arr = list(map(int, input().strip().split()))
a = [0] * n
k = pow(10, 9) + 7
a[0] = pow(2, n, k) - 1
for i in range(1, int((n + 1) / 2)):
	a[i] = (a[i - 1] + pow(2, n - i - 1, k) - pow(2, i - 1, k)) % k
i = -1
for _ in range(int(n / 2)):
	a[i] = a[abs(i) - 1]
	i -= 1
s = 0
for i in range(n):
	s = (s + a[i] * arr[i] % k) % k
print(s)


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def rangesum(i, j, prefixes):
	return prefixes[j] - (0 if i == 0 else prefixes[i - 1])
n = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]
dp = [None for _ in range(n)]
dp[-1] = (A[-1], 1, 1, A[-1])
prefixes = [0 for _ in range(n)]
prefixes[0] = A[0]
for i in range(1, n):
	prefixes[i] = prefixes[i - 1] + A[i]
for i in range(n - 2, -1, -1):
	(last_x, last_y, last_z, last_a) = dp[i + 1]
	exc_x = add(last_x, mul(A[i], last_y))
	inc_x = add(last_x, add(last_a, mul(A[i], add(last_z, last_y))))
	x = add(exc_x, inc_x)
	y = mul(last_y, 2)
	z = add(last_z, mul(last_y, 2))
	a = add(mul(2, mul(A[i], last_y)), last_a)
	dp[i] = (x, y, z, a)
print(dp[0][0])


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys

def get_size():
	n = input()
	n = int(n)
	return n

def get_arr():
	arry = input().split(' ')
	arr = []
	h = 0
	return arry

def calculate_arr_value(arr, indexes):
	tot_sum = 0
	loc_sum = 0
	arr_i = 0
	h = 0
	while h <= len(indexes) - 1:
		loc_sum = 0
		if indexes[h] > 1:
			g = 0
			while g <= indexes[h] - 1:
				loc_sum = loc_sum + arr[g + arr_i]
				g = g + 1
			loc_sum = loc_sum * indexes[h]
			arr_i = arr_i + g
		else:
			loc_sum = arr[arr_i]
		tot_sum = tot_sum + loc_sum
		arr_i = arr_i + 1
		h = h + 1
	print(arr, tot_sum)
	return tot_sum

def __main__():
	n = get_size()
	arr = get_arr()
	counts = []
	p = pow(2, n, 1000000007) - 1
	counts.append(p)
	summ = 0
	summ = summ + counts[0] * int(arr[0])
	y = n - 2
	if n % 2 == 0:
		b = n / 2
	else:
		b = n / 2 + 1
		b = int(b)
	h = 1
	a = 0
	while h <= b - 1:
		p = p + pow(2, y, 1000000007) - pow(2, a, 1000000007)
		summ = summ + p * int(arr[h])
		counts.append(p)
		a = a + 1
		y = y - 1
		h = h + 1
	d = b
	while d <= len(arr) - 1:
		summ = summ + counts[len(arr) - 1 - int(d)] * int(arr[int(d)])
		d = d + 1
	print(summ % 1000000007)
__main__()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


N = int(input())
A = list(map(int, input().strip().split()))
MOD = 1000000007

def solve(A):
	N = len(A)
	if N == 0:
		return 0
	dp = (A[0], 1, A[0], 1)
	for i in range(1, N):
		(prevx, prevnsuff, prevsumsuff, prevlensuff) = dp
		newx1 = (prevx + A[i] * prevnsuff) % MOD
		newx2 = (prevx + prevsumsuff) % MOD + A[i] * (prevlensuff + prevnsuff) % MOD
		newx = (newx1 + newx2) % MOD
		newnsuff = 2 * prevnsuff % MOD
		newlensuff = prevlensuff + 2 * prevnsuff % MOD
		newsumsuff = prevsumsuff + newnsuff * A[i] % MOD
		dp = (newx, newnsuff, newsumsuff, newlensuff)
	return dp[0] % MOD
print(solve(A))


n = int(input())
M = int(1000000000.0 + 7)
A = [int(m) for m in input().strip().split()]
if len(A) == 1:
	print(A[0])
else:
	T = [0, A[0]]
	S = [0]
	for i1 in range(n):
		S.append(S[-1] + A[i1])
	P = [None]
	P.append(0)
	for i1 in range(2, n + 1):
		P.append((pow(2, i1 - 2, M) * S[i1 - 1] + P[-1]) % M)
		T.append((2 * T[-1] + pow(2, i1 - 1, M) * S[i1] + (pow(2, i1 - 1, M) - 1) * A[i1 - 1] - P[-1]) % M)
	print(T[-1] % M)


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys

def sumcalc(iput, n):
	coeff = []
	multi = []
	temp = pow(2, n, 1000000007) - 1
	coeff.append(temp)
	if n % 2 == 0:
		k = n / 2
		k = int(k)
	else:
		k = (n + 1) / 2
		k = int(k)
	for j in range(1, k + 1):
		nxtval = (coeff[j - 1] + pow(2, n - 2 - (j - 1), 1000000007) - pow(2, j - 1, 1000000007)) % (pow(10, 9) + 7)
		coeff.append(nxtval)
		nxtval = 0
	multi = []
	diff = n - 1
	for l in range(0, k):
		tem = iput[l] * coeff[l] % (pow(10, 9) + 7)
		multi.append(tem)
		if diff > l:
			tem = iput[diff] * coeff[l] % (pow(10, 9) + 7)
			multi.append(tem)
		diff = diff - 1
	finval = sum(multi) % (pow(10, 9) + 7)
	print(finval)

def main():
	lth = int(sys.stdin.readline())
	tm = input()
	iput = []
	t_iput = tm.split()
	iput = [int(l) for l in t_iput]
	sumcalc(iput, lth)
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]
n = int(input())
A = list(map(int, input().split(' ')))
print(pieces(A))


MODULUS = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().strip().split(' ')))

def mod_sum(iterable):
	summ = 0
	for x in iterable:
		summ += x
		summ %= MODULUS
	return summ

def mod_mul(a, b):
	return a * b % MODULUS

def mod_mersenne(n):
	return (2 ** n - 1) % MODULUS

def mod_wierd(i, n):
	n -= 1
	i -= 1
	if i == -1:
		return 1
	import math
	a = math.factorial(n)
	b = math.factorial(i)
	c = math.factorial(n - i)
	return 2 ** (n - i) * (a // (b * c)) % MODULUS

def mod_occurrences(i, n):
	return (mod_wierd(i, n - 1) + mod_mersenne(n) - 1) % MODULUS

def sum_pieces(n, a):
	previous_sum = 0
	power_sum = 0
	previous_first = 0
	previous_power = 1
	for (i, last) in enumerate(a):
		next_sum = 2 * previous_sum + power_sum + (2 * previous_first + 1) * last
		power_sum += previous_power * last % MODULUS
		previous_sum = next_sum % MODULUS
		previous_first = (2 * previous_first + 1) % MODULUS
		previous_power = 2 * previous_power % MODULUS
	return previous_sum
print(sum_pieces(n, a))


n = int(input())
l = list(map(int, input().split()))
res = 0
r = list()
r.append(pow(2, n, 10 ** 9 + 7) - 1)
for i in range(1, n):
	r.append(r[i - 1] + pow(2, n - i - 1, 10 ** 9 + 7) - pow(2, i - 1, 10 ** 9 + 7))
print(sum([l[i] * r[i] % (10 ** 9 + 7) for i in range(n)]) % (10 ** 9 + 7))


n = int(input().strip())
modulo = 10 ** 9 + 7
p = n - 2
s = n - 2
l = n // 2
slist = input().strip().split(' ')
a = int(slist[0])
if n == 1:
	print(a)
else:
	cnts = []
	cnt = pow(2, n, modulo) - 1
	cnts.append(cnt)
	total = cnt * a % modulo
	i = 0
	for i in range(1, l):
		a = int(slist[i])
		cnt = (cnt + pow(2, p, modulo) - pow(2, s - p, modulo)) % modulo
		cnts.append(cnt)
		total = (total + cnt * a) % modulo
		p = p - 1
	if n % 2 != 0:
		i = i + 1
		a = int(slist[i])
		cnt = (cnt + pow(2, p, modulo) - pow(2, s - p, modulo)) % modulo
		total = (total + cnt * a) % modulo
		l = l + 1
	d = n - 1
	for i in range(l, n):
		a = int(slist[i])
		total = (total + cnts[d - i] * a) % modulo
	print(total)


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD
n = int(input())
str = input().split()
a = [None] * n
for i in range(n):
	a[i] = int(str[i])
dp = (a[0], 1, 1, a[0])
for i in range(1, n):
	(last_x, last_y, last_k, last_m) = dp
	exc_x = add(last_x, mul(a[i], last_y))
	inc_x = add(last_x, add(last_m, mul(a[i], add(last_k, last_y))))
	x = add(exc_x, inc_x)
	y = mul(last_y, 2)
	k = add(last_k, y)
	m = add(mul(a[i], y), last_m)
	dp = (x, y, k, m)
print(dp[0])


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().strip().split()))
rslt = 0
mod = 10 ** 9 + 7
for (idx, val) in enumerate(arr):
	coeff = (pow(2, n, mod) + pow(2, n - 1, mod) - pow(2, n - idx - 1, mod) - pow(2, idx, mod)) % mod
	rslt += coeff * val % mod
	rslt %= mod
print(rslt)


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys

def solve_bf(aa):

	def groups_gen():
		st = [[1]]
		while True:
			yield st
			new_st = []
			for u in st:
				v = u + [1]
				w = list(u)
				w[-1] += 1
				new_st.append(v)
				new_st.append(w)
			st = new_st

	def aggregate(gg):
		rval = [0] * sum(gg[0])
		for g in gg:
			i = 0
			for u in g:
				for j in range(u):
					rval[i + j] += u
				i += u
		return rval
	agg = None
	for (i, gg) in enumerate(groups_gen()):
		agg = aggregate(gg)
		print('agg=%s' % (agg,), file=sys.stderr)
		if i + 1 == len(aa):
			break
	return sum((u * v for (u, v) in zip(aa, agg)))

def solve_bf1(aa, modulo):

	def gen():
		cache = [1]
		while True:
			yield cache
			new_cache = []
			(c, halfc) = (1, 1)
			l = (len(cache) + 1) // 2
			i = 0
			for i in range(l):
				u = cache[i]
				v = 2 * cache[i] + c
				v %= modulo
				new_cache.append(v)
				halfc = c
				c *= 2
				c %= modulo
			if len(cache) % 2 == 0:
				u = new_cache and new_cache[-1] or cache[-1]
				v = (u + halfc) % modulo
				new_cache.append(v)
				for i in range(len(new_cache) - 2, -1, -1):
					new_cache.append(new_cache[i])
			else:
				for i in range(len(new_cache) - 1, -1, -1):
					new_cache.append(new_cache[i])
			cache = new_cache
	for (i, cache) in enumerate(gen()):
		if i + 1 == len(aa):
			break
	sm = 0
	for (u, v) in zip(aa, cache):
		sm += u * v % modulo
		sm %= modulo
	return sm

def get_a(i, p, modulo):
	if i < p:
		return None
	u = pow(2, i - p, modulo)
	v = pow(2, p + 1, modulo)
	w = pow(2, p, modulo)
	rval = u * (v - 1) + w * (u - 1)
	return rval % modulo

def solve(aa, modulo):
	cache = [get_a(len(aa) - 1, p, modulo) for p in range(len(aa))]
	sm = 0
	for (u, v) in zip(aa, cache):
		sm += u * v % modulo
		sm %= modulo
	return sm
n = int(input())
aa = list(map(int, input().split()))
modulo = pow(10, 9) + 7
print(solve(aa, modulo))


n = int(input().strip())
arr = list(map(int, input().strip().split(' ')))
c = []
base = pow(2, n, 10 ** 9 + 7)
c.append(base - 1)
upper = n // 2 if n % 2 == 0 else n // 2 + 1
if n > 1:
	upper = n // 2 if n % 2 == 0 else n // 2 + 1
	for i in range(1, upper):
		c.append(base + pow(2, n - 1, 10 ** 9 + 7) - pow(2, n - i - 1, 10 ** 9 + 7) - pow(2, i, 10 ** 9 + 7))
res = 0
for i in range(n):
	if i < upper:
		coefficient = c[i]
	elif n % 2 == 0:
		coefficient = c[upper - i - 1]
	else:
		coefficient = c[upper - i - 2]
	res += arr[i] * coefficient
	res = res % (10 ** 9 + 7)
print(int(res))


import sys
Mod = 10 ** 9 + 7

def summingPieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(l_x, l_y, l_k, l_m) = dp
		e_x = (l_x + A[i] * l_y % Mod) % Mod
		i_x = (l_x + (l_m + A[i] * ((l_k + l_y) % Mod) % Mod) % Mod) % Mod
		x = (e_x + i_x) % Mod
		y = l_y * 2 % Mod
		k = (l_k + y) % Mod
		m = (A[i] * y % Mod + l_m) % Mod
		dp = (x, y, k, m)
	return dp[0]
n = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]
print(summingPieces(A))


n = 10 ** 6 + 3
s_array = [1]
mod = 10 ** 9 + 7
for i in range(1, n):
	s_array.append(s_array[i - 1] * 2 % mod)
size = int(input())
array = list(map(int, input().split()))
m_array = [0] * size
start = size - 2
m_array[0] = m_array[-1] = (s_array[size] - 1 + mod) % mod
for i in range(1, size // 2 + 1):
	m_array[i] = (s_array[start] - s_array[i - 1] + mod) % mod
	m_array[i] = (m_array[i - 1] + m_array[i]) % mod
	m_array[-i - 1] = m_array[i]
	start -= 1
ans = 0
for i in range(size):
	ans = (ans + m_array[i] * (array[i] % mod) % mod) % mod
print(ans)


n = 10 ** 6 + 3
s_array = [1]
mod = 10 ** 9 + 7
for i in range(1, n):
	s_array.append(s_array[i - 1] * 2 % mod)
size = int(input())
array = list(map(int, input().split()))
m_array = [0] * size
start = size - 2
m_array[0] = m_array[-1] = (s_array[size] - 1 + mod) % mod
for i in range(1, size // 2 + 1):
	m_array[i] = (s_array[start] - s_array[i - 1] + mod) % mod
	m_array[i] = (m_array[i - 1] + m_array[i]) % mod
	m_array[-i - 1] = m_array[i]
	start -= 1
ans = 0
for i in range(size):
	ans = (ans + m_array[i] * (array[i] % mod) % mod) % mod
print(ans)


from collections import deque

def sum_pieces(n, ar):
	mod = 10 ** 9 + 7
	q = deque(ar)
	p = pow(2, n, mod) - 1
	total = p * (q.popleft() + q.pop())
	y = n - 2
	for i in range(1, n // 2):
		p += pow(2, y, mod) - pow(2, i - 1, mod)
		total += p * (q.popleft() + q.pop())
		y -= 1
	if len(q) > 0:
		p += pow(2, y, mod) - pow(2, n // 2 - 1, mod)
		total += p * ar[n // 2]
	return total % mod

def main():
	n = int(input())
	ar = list(map(int, input().split()))
	result = sum_pieces(n, ar)
	print(result)
main()


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


n = int(input())
arr = list(map(int, input().strip().split()))
mod = 10 ** 9 + 7
(int_sum, suf_sum, suf_len, combs) = (arr[0], arr[0], 1, 1)
for i in range(1, n):
	int_sum += int_sum + suf_sum + arr[i] * (suf_len + combs + combs)
	combs += combs
	suf_len += combs
	suf_sum += arr[i] * combs
	int_sum %= mod
	suf_sum %= mod
	suf_len %= mod
	combs %= mod
print(int_sum)


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


n = int(input())
xs = [int(x) for x in input().split()]

def count_n(n):
	if n == 0:
		return 1
	return 2 ** (n - 1)

def solve(xs):
	if len(xs) == 1:
		return xs[0]
	a = sum(xs) * len(xs)
	for i in range(1, len(xs)):
		a += solve(xs[:i]) + count_n(i) * sum(xs[i:]) * (len(xs) - i)
	return a
sums = [xs[0]]
for x in xs[1:]:
	sums.append(sums[-1] + x)
res = xs[0]
sres = res
s_count = res
s_count_len = res
count = 1
count_len = 1
sums = 0
mod = 10 ** 9 + 7
for (i, x) in list(enumerate(xs))[1:]:
	length = i + 1
	count = (count + pow(2, i - 1, mod)) % mod
	count_len = (count_len + count) % mod
	s_count_len = (s_count_len + s_count + count_len * x) % mod
	s_count = (s_count + count * x) % mod
	res = (sres + s_count_len) % mod
	sres += res
print(res)


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


n = int(input().strip())
A = [int(_) for _ in input().strip().split()]
a = A[0]
if n == 1:
	print(a)
else:
	t = A[0]
	ratio = 2
	for i in range(1, n):
		a = (2 * a + t + A[i] * (ratio * 2 - 1)) % (10 ** 9 + 7)
		t = (t + A[i] * ratio) % (10 ** 9 + 7)
		ratio = ratio * 2 % (10 ** 9 + 7)
	print(a)


MOD = 10 ** 9 + 7
n = int(input())
nums = list(map(int, input().split()))
tot = 0
spl = nums[0]
add = nums[0]
mult = 1
n = 1
for z in nums[1:]:
	new_tot = (2 * tot + add) % MOD
	new_mult = (mult + 2 * n) % MOD
	new_add = (add + spl + z * new_mult) % MOD
	new_spl = (spl + 2 * n * z) % MOD
	new_n = 2 * n % MOD
	(tot, spl, add, mult, n) = (new_tot, new_spl, new_add, new_mult, new_n)
print((tot + add) % MOD)


n = int(input())
a = map(int, input().split())
M = 1000000007
dp = [0]
n_sums = 0
power_sums = 0
two_powers = 1
j = 0
for i in a:
	j += 1
	dp.append(2 * dp[j - 1])
	n_sums += two_powers
	dp[j] += power_sums + n_sums * i
	power_sums += two_powers * i
	two_powers *= 2
	n_sums %= M
	dp[j] %= M
	power_sums %= M
	two_powers %= M
print(dp[j])


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


from math import ceil
n = int(input())
arr = list(map(int, input().split()))
base = 7 + 10 ** 9
coeff = [0]
coeff[0] = (pow(2, n, base) - 1) % base
val = 0
for i in range(1, int(ceil(n / 2))):
	coeff.append((coeff[i - 1] + pow(2, n - 1 - i, base) - pow(2, i - 1, base)) % base)
if n % 2 == 0:
	temp = coeff[:]
	temp.reverse()
	for i in temp:
		coeff.append(i)
else:
	temp = coeff[:]
	temp.reverse()
	p = len(temp)
	for i in range(1, p):
		coeff.append(temp[i])
for i in range(n):
	val = (val + arr[i] * coeff[i]) % base
print(val)


N = 10 ** 9 + 7
k = int(input()) - 1
calc0 = 0
calc1 = 0
calc2 = 0
near_total = 0
sumA = 0
i = 0
f = 1
value = 0
for x in map(int, input().split()):
	sumA += x
	i += 1
	near_total = (2 * near_total + value) % N
	value = sumA * (i * f - calc0) + calc1 - i * calc2
	calc0 = (calc0 + i * f) % N
	calc1 = (calc1 + i * f * sumA) % N
	calc2 = (calc2 + f * sumA) % N
	f = 2 * f % N
print((near_total + value) % N)


n = int(input())
a = list(map(int, input().split()))
p = 1000000007
sum = 0
prev = 0
pow2 = [1]
for i in range(1, n + 1):
	pow2.append(pow2[i - 1] * 2 % p)
prev = (pow2[n] - 1) % p
sum = prev * a[0]
for i in range(1, n - 1):
	prev = ((prev + pow2[n - i - 1]) % p - pow2[i - 1]) % p
	sum = (sum + prev * a[i] % p) % p
prev = (pow2[n] - 1) % p
sum = (sum + prev * a[n - 1] % p) % p
print(sum)


import sys
n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
res = 0
r = []
r.append(pow(2, n, 10 ** 9 + 7) - 1)
for i in range(1, n):
	r.append(r[i - 1] + pow(2, n - i - 1, 10 ** 9 + 7) - pow(2, i - 1, 10 ** 9 + 7))
print(sum([a[i] * r[i] % (10 ** 9 + 7) for i in range(n)]) % (10 ** 9 + 7))


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


import sys
MOD = 1000000007

def mul(a, b):
	return a * b % MOD

def add(a, b):
	return (a + b) % MOD

def pieces(A):
	n = len(A)
	if n == 0:
		return 0
	dp = (A[0], 1, 1, A[0])
	for i in range(1, n):
		(last_x, last_y, last_k, last_m) = dp
		exc_x = add(last_x, mul(A[i], last_y))
		inc_x = add(last_x, add(last_m, mul(A[i], add(last_k, last_y))))
		x = add(exc_x, inc_x)
		y = mul(last_y, 2)
		k = add(last_k, y)
		m = add(mul(A[i], y), last_m)
		dp = (x, y, k, m)
	return dp[0]

def main():
	n = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	print(pieces(A))
main()


INF = 1000000007
n = int(input())
arr = list(map(int, input().split(' ')))
j = n - 2
lst = []
ans = []
count_init = pow(2, n, INF) - 1
lst.append(count_init)
ans.append(count_init * arr[0] % INF)
for i in range(1, n):
	val = lst[i - 1] + pow(2, j, INF) - pow(2, i - 1, INF)
	lst.append(val)
	ans.append(val * arr[i] % INF)
	j -= 1
print(sum(ans) % INF)


import sys

def main(n, array):
	mod = int(1000000000.0) + 7
	list = [1]
	power2 = 1
	for i in range(1, len(array) + 1):
		list.append(list[i - 1] * 2 % mod)
	coeffcient = list[len(array)] - 1
	coeffcient %= mod
	answer = coeffcient * array[0]
	answer %= mod
	answer += coeffcient * array[len(array) - 1]
	answer %= mod
	for i in range(1, len(array) // 2):
		coeffcient += list[n - i - 1]
		coeffcient %= mod
		coeffcient -= list[i - 1]
		coeffcient %= mod
		answer += coeffcient * (array[i] % mod) % mod
		answer %= mod
		answer += coeffcient * (array[len(array) - i - 1] % mod) % mod
		answer %= mod
	if len(array) % 2 == 1:
		coeffcient += list[n - len(array) // 2 - 1]
		coeffcient %= mod
		coeffcient -= list[len(array) // 2 - 1]
		coeffcient %= mod
		answer += coeffcient * array[len(array) // 2]
	answer %= mod
	print(answer)
n = int(input())
array = list(map(int, input().strip().split(' ')))
main(n, array)


n = int(input())
a = map(int, input().split(' '))
m = 10 ** 9 + 7
p = pow(2, n, m) - 1
y = n - 2
s = 0
i = 0
for v in a:
	s += v * p
	s %= m
	if y >= i:
		p += pow(2, y - i, 2 * m) - pow(2, i, 2 * m)
		p %= m
		i += 1
print(s)


import os
import sys

def summingPieces(arr):
	n = len(arr)
	MODULO = 10 ** 9 + 7
	two_degs = [1 for i in range(n + 1)]
	for i in range(n):
		two_degs[i + 1] = two_degs[i] * 2 % MODULO
	coeffs = [-1 for i in range(n)]
	coeffs[0] = two_degs[n] - 1
	for i in range(1, (n + 1) // 2):
		coeffs[i] = (coeffs[i - 1] - two_degs[i - 1] + two_degs[n - 1 - i]) % MODULO
	for i in range((n + 1) // 2, n):
		coeffs[i] = coeffs[n - 1 - i]
	res = 0
	for (c, a) in zip(coeffs, arr):
		res += c * a % MODULO
		res %= MODULO
	return res
arr_count = int(input())
arr = list(map(int, input().rstrip().split()))
result = summingPieces(arr)
print(str(result))


n = 10 ** 6 + 3
s_array = [1]
mod = 10 ** 9 + 7
for i in range(1, n):
	s_array.append(s_array[i - 1] * 2 % mod)
size = int(input())
array = list(map(int, input().split()))
m_array = [0] * size
start = size - 2
m_array[0] = m_array[-1] = (s_array[size] - 1 + mod) % mod
for i in range(1, size // 2 + 1):
	m_array[i] = (s_array[start] - s_array[i - 1] + mod) % mod
	m_array[i] = (m_array[i - 1] + m_array[i]) % mod
	m_array[-i - 1] = m_array[i]
	start -= 1
ans = 0
for i in range(size):
	ans = (ans + m_array[i] * (array[i] % mod) % mod) % mod
print(ans)