HackerRank-city is an acyclic connected graph (or tree). Its not an ordinary place, the construction of the whole tree takes place in $N$ steps. The process is described below:

It initially has $\mbox{1}$ node.
At each step, you must create $3$ duplicates of the current tree, and create $2$ new nodes to connect all $\begin{array}{c}4\end{array}$ copies in the following H shape:

At each $i^{\mbox{th}}$ step, the tree becomes $\begin{array}{c}4\end{array}$ times bigger plus $2$ new nodes, as well as $5$ new edges connecting everything together. The length of the new edges being added at step $\boldsymbol{i}$ is denoted by input $A_i$.

Calculate the sum of distances between each pair of nodes; as these answers may run large, print your answer modulo $\textbf{1000000007}$.

Input Format

The first line contains an integer, $N$ (the number of steps). The second line contains $N$ space-separated integers describing  $\boldsymbol{A_0}$, $A_1,\ldots,A_{N-2},A_{N-1}$.

Constraints

$1\leq N\leq10^6$

$1\leq A_i\leq9$

Subtask 

For $50\%$ score $1\leq N\leq10$

Output Format

Print the sum of distances between each pair of nodes modulo $\textbf{1000000007}$.

Sample Input 0

1
1

Sample Output 0

29

Sample Input 1

2
2 1

Sample Output 1

2641

Explanation

Sample 0

In this example, our tree looks like this:

Let $d(u,v)$ denote the distance between nodes $\mbox{u}$ and $\boldsymbol{\nu}$.

$d(1,2)+d(1,3)+d(1,4)+d(1,5)+d(1,6)$
$+d(2,3)+d(2,4)+d(2,5)+d(2,6)+d(3,4)$
$+d(3,5)+d(3,6)+d(4,5)+d(4,6)+d(5,6)=$
$3+1+2+2+3+2+1+3+2+1+1+2+2+1+3=29$.     

We print the result of $29\{%10000007$ as our answer.

Sample 1

In this example, our tree looks like this:

We calculate and sum the distances between nodes in the same manner as Sample 0 above, and print the result of our $answer\% 10000007}$, which is $2641$.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
inp = sys.stdin
n = int(inp.readline().strip())
lengths = list(map(int, inp.readline().strip().split(' ')))
f = 0
g = 0
h = 0
m = 1
for a in lengths:
	f = (4 * g * (3 * m + 2) + 4 * f + 16 * a * m * m + 12 * a * m + a) % 1000000007
	g = (4 * g + m * (3 * h + 8 * a) + 2 * h + 3 * a) % 1000000007
	h = (2 * h + 3 * a) % 1000000007
	m = (4 * m + 2) % 1000000007
print(f)


n_iters = int(input())
final_wt = 0
x0 = 0
d0 = 0
w0 = 0
n0 = 1
e0 = 0
wts = [int(val) for val in input().strip().split()]
for depth in range(n_iters):
	e1 = wts[depth]
	x1 = (4 * x0 + e1 * (8 * n0 + 3) + d0 * (3 * n0 + 2)) % 1000000007
	d1 = (2 * d0 + 3 * e1) % 1000000007
	w1 = (n0 * (12 * x0 + e1 * (16 * n0 + 12)) + 4 * w0 + 8 * x0 + e1) % 1000000007
	n1 = (n0 * 4 + 2) % 1000000007
	x0 = x1
	d0 = d1
	w0 = w1
	n0 = n1
	final_wt = w1
print(final_wt % 1000000007)


import sys
modulo = 10 ** 9 + 7

def next_step(prev_sum, pn, plrs, e):
	sum_inside_replicas = 4 * prev_sum % modulo
	sum_outer = (12 * pn * plrs + 16 * e * pn * pn) % modulo
	sum_to_connection = (8 * plrs + 12 * pn * e) % modulo
	return (sum_inside_replicas + e + sum_outer + sum_to_connection) % modulo

def get_sum(n, edges):
	cur_n = 1
	cur_sum = 0
	cur_diameter = 0
	cur_lower_right_sum = 0
	for i in range(n):
		next_sum = next_step(cur_sum, cur_n, cur_lower_right_sum, edges[i])
		cur_lower_right_sum = (4 * cur_lower_right_sum + cur_n * (3 * cur_diameter + 8 * edges[i]) + 2 * cur_diameter + edges[i] * 3) % modulo
		cur_n = (cur_n * 4 + 2) % modulo
		cur_sum = next_sum
		cur_diameter = (2 * cur_diameter + 3 * edges[i]) % modulo
	return cur_sum
_N = int(sys.stdin.readline().strip())
_edges_line = sys.stdin.readline().strip()
_EDGES = [int(edge) for edge in _edges_line.split()]
print(get_sum(_N, _EDGES))


N = int(input())
A = [int(x) for x in input().split()]
S = 29 * A[0]
L = 11 * A[0]
LL = 3 * A[0]
M = 1000000007
n = 6
for i in range(1, N):
	na = n * A[i]
	na2 = na + na
	L2 = (L + L) % M
	na2L = (na2 + L2) % M
	S = (4 * (S + na + na2L + n * (na2L + na)) + 2 * n * na2L + A[i]) % M
	L = (L2 + 2 * (3 * na + n * LL) + na2L + n * LL + 3 * A[i] + 2 * LL) % M
	LL = (LL + LL + 3 * A[i]) % M
	n = (4 * n + 2) % M
print(S)


n = int(input())
a = [int(x) for x in input().split(' ')]
v = 1
ans = 0
d = 0
diam = 0
mod = 1000000007
for x in a:
	tempv = v * 4 + 2
	tempans = 4 * ans + 4 * d * (2 + 3 * v % mod) % mod + 16 * x % mod * v % mod * v % mod + 12 * x % mod * v % mod + x
	tempd = 4 * d + 8 * x * v % mod + 3 * x + diam * (3 * v + 2) % mod
	tempdiam = 2 * diam + 3 * x
	v = tempv % mod
	ans = tempans % mod
	d = tempd % mod
	diam = tempdiam % mod
print(ans)


n = int(input())
A = list(map(int, input().split(' ')))
mod = 1000000007
v = (0, 0, 1, 0)
for i in range(n):
	tmp1 = 4 * v[0] + 8 * v[1] + 12 * v[1] * v[2] + 16 * A[i] * v[2] * v[2] + 12 * A[i] * v[2] + A[i]
	tmp2 = 4 * v[1] + 2 * v[3] + 3 * v[2] * v[3] + 3 * A[i] + 8 * A[i] * v[2]
	tmp3 = 4 * v[2] + 2
	tmp4 = 2 * v[3] + 3 * A[i]
	v = (tmp1 % mod, tmp2 % mod, tmp3 % mod, tmp4 % mod)
print(v[0])


n = int(input().strip())
edgeCostsArr = [int(x) for x in input().split()]
numNodesArr = [6]
totalCostArr = [29 * edgeCostsArr[0]]
terminalCostArr = [11 * edgeCostsArr[0]]
endToEndArr = [3 * edgeCostsArr[0]]

def getCostForLevel(level):
	for i in range(1, level):
		totalCost = 0
		totalCost += totalCostArr[i - 1] * 4
		totalCost += terminalCostArr[i - 1] * numNodesArr[i - 1] * 2 * 6
		totalCost += edgeCostsArr[i] * 16 * numNodesArr[i - 1] * numNodesArr[i - 1]
		totalCost += (terminalCostArr[i - 1] + edgeCostsArr[i] * numNodesArr[i - 1]) * 4
		totalCost += (terminalCostArr[i - 1] + edgeCostsArr[i] * numNodesArr[i - 1] * 2) * 4
		totalCost += edgeCostsArr[i]
		totalCostArr.append(totalCost % 1000000007)
		terminalCost = 0
		terminalCost += terminalCostArr[i - 1] * 4
		terminalCost += (3 * edgeCostsArr[i] + endToEndArr[i - 1]) * numNodesArr[i - 1]
		terminalCost += (2 * edgeCostsArr[i] + endToEndArr[i - 1]) * numNodesArr[i - 1]
		terminalCost += (3 * edgeCostsArr[i] + endToEndArr[i - 1]) * numNodesArr[i - 1]
		terminalCost += endToEndArr[i - 1] * 2 + edgeCostsArr[i] * 3
		terminalCostArr.append(terminalCost % 1000000007)
		endToEndArr.append((endToEndArr[i - 1] * 2 + edgeCostsArr[i] * 3) % 1000000007)
		numNodesArr.append((numNodesArr[i - 1] * 4 + 2) % 1000000007)
	return totalCostArr[level - 1] % 1000000007
print(getCostForLevel(n))


MOD = 10 ** 9 + 7
N = int(input())
(n, D, d, l) = (1, 0, 0, 0)
for a in map(int, input().split()):
	(n, D, d, l) = (4 * n + 2, 4 * D + (3 * n + 2) * l + (8 * n + 3) * a, 16 * a * n * n + n * 12 * (D + a) + 8 * D + a + 4 * d, 2 * l + 3 * a)
	n %= MOD
	D %= MOD
	d %= MOD
	l %= MOD
print(d % MOD)


n = int(input())
cost = [int(i) for i in input().split()]
cost = [1] + cost
count = [0] * (n + 1)
diag = [0] * (n + 1)
junction = [0] * (n + 1)
full = [0] * (n + 1)
count[0] = 1
diag[0] = 0
junction[0] = 0
full[0] = 0
count[1] = 6
diag[1] = 3 * cost[1]
junction[1] = 11 * cost[1]
full[1] = 29 * cost[1]
for i in range(2, n + 1):
	count[i] = (count[i - 1] * 4 + 2) % 1000000007
	diag[i] = (2 * diag[i - 1] + 3 * cost[i]) % 1000000007
	junction[i] = (2 * (junction[i - 1] + count[i - 1] * (3 * cost[i] + diag[i - 1])) + junction[i - 1] + count[i - 1] * (2 * cost[i] + diag[i - 1]) + junction[i - 1] + 3 * cost[i] + 2 * diag[i - 1]) % 1000000007
	full[i] = (full[i - 1] * 4 + 4 * (junction[i - 1] * count[i - 1] * 2 + count[i - 1] * count[i - 1] * 3 * cost[i]) + 2 * (junction[i - 1] * count[i - 1] * 2 + count[i - 1] * count[i - 1] * 2 * cost[i]) + 8 * junction[i - 1] + count[i - 1] * cost[i] * 12 + cost[i]) % 1000000007
print(full[n] % 1000000007)


def compute(A):
	S = 1
	D = 0
	E = 0
	F = 0
	M = 10 ** 9 + 7
	for n in range(1, len(A) + 1):
		Sn = 4 * S + 2
		Dn = 2 * D + 3 * A[n - 1]
		En = 4 * E + (3 * S + 2) * D + (3 + 8 * S) * A[n - 1]
		Fn = 4 * F + (12 * S + 8) * E + (12 * S + 16 * S * S + 1) * A[n - 1]
		S = Sn % M
		D = Dn % M
		E = En % M
		F = Fn % M
	return F
n = int(input())
A = [int(x) for x in input().split()]
print(compute(A))


n = int(input())
array = [int(i) for i in input().split()]
assert 1 <= n <= 10 ** 6
assert all([1 <= x <= 9 for x in array])
M = 10 ** 9 + 7
(curSum, curSumFromVertex, curVertexCount, height) = (0, 0, 1, 0)
for a in array:
	newYSum = (curSumFromVertex + a * curVertexCount) * 2 + (curSumFromVertex + 2 * a * curVertexCount) * 2 + a
	newSumFromVertex = curSumFromVertex + (curSumFromVertex + (height + 2 * a) * curVertexCount) + 2 * (curSumFromVertex + (height + 3 * a) * curVertexCount) + height + a + height + 2 * a
	newSum1 = 2 * (2 * curSumFromVertex * curVertexCount + 2 * a * curVertexCount * curVertexCount)
	newSum2 = 4 * (2 * curSumFromVertex * curVertexCount + 3 * a * curVertexCount * curVertexCount)
	curSum = newSum1 + newSum2 + newYSum * 2 - a + curSum * 4
	curSumFromVertex = newSumFromVertex
	height = height * 2 + 3 * a
	curVertexCount = curVertexCount * 4 + 2
	curSum %= M
	curSumFromVertex %= M
	curVertexCount %= M
	height %= M
print(curSum)


class city(object):

	def __init__(self, A, num_iterations):
		self.num_nodes = 1
		self.corner_num_nodes = 0
		self.sum_to_corner = 0
		self.next_sum_to_corner = 0
		self.total_path_sums = 0
		self.corner_diameter = 0
		self.A = A
		self.num_iterations = num_iterations
		self.current_iteration = 0
		self.M = 1000000007

	def get_next_num_nodes(self):
		return 4 * self.num_nodes + 2

	def get_next_corner_num_nodes(self):
		return self.num_nodes

	def get_next_sum_to_corner(self, new_A):
		c1 = self.sum_to_corner + 3 * self.num_nodes * new_A + self.num_nodes * self.corner_diameter
		c2 = self.sum_to_corner + 2 * self.num_nodes * new_A + self.num_nodes * self.corner_diameter
		c3 = self.sum_to_corner + 3 * self.num_nodes * new_A + self.num_nodes * self.corner_diameter
		c4 = self.sum_to_corner
		middle_node_1 = new_A + self.corner_diameter
		middel_node_2 = 2 * new_A + self.corner_diameter
		return c1 + c2 + c3 + c4 + middle_node_1 + middel_node_2

	def get_next_corner_diameter(self, new_A):
		return 2 * self.corner_diameter + 3 * new_A

	def run_iteration(self):
		new_A = self.A[self.current_iteration]
		new_nodes = self.get_next_num_nodes()
		new_corner_nodes = self.get_next_corner_num_nodes()
		new_sum_to_corner = self.get_next_sum_to_corner(new_A)
		self.num_nodes = new_nodes
		self.corner_num_nodes = new_corner_nodes
		self.next_sum_to_corner = new_sum_to_corner
		self.total_path_sums = self.calculate_total_path_sums(new_A)
		self.corner_diameter = self.get_next_corner_diameter(new_A)
		self.sum_to_corner = self.next_sum_to_corner
		self.current_iteration += 1
		self.num_nodes %= self.M
		self.sum_to_corner %= self.M
		self.total_path_sums %= self.M
		self.corner_diameter %= self.M

	def calculate_total_path_sums(self, new_A):
		prev_sum = self.total_path_sums
		sums_within_corners = 4 * prev_sum
		sum_within_middle = new_A
		sum_centers_to_corners = 4 * (2 * self.sum_to_corner + new_A * 3 * self.corner_num_nodes)
		sum_c1c2 = new_A * 3 * self.corner_num_nodes ** 2 + 2 * self.sum_to_corner * self.corner_num_nodes
		sum_c1c3 = new_A * 2 * self.corner_num_nodes ** 2 + 2 * self.sum_to_corner * self.corner_num_nodes
		sum_c1c4 = new_A * 3 * self.corner_num_nodes ** 2 + 2 * self.sum_to_corner * self.corner_num_nodes
		sum_c2c3 = new_A * 3 * self.corner_num_nodes ** 2 + 2 * self.sum_to_corner * self.corner_num_nodes
		sum_c2c4 = new_A * 2 * self.corner_num_nodes ** 2 + 2 * self.sum_to_corner * self.corner_num_nodes
		sum_c3c4 = new_A * 3 * self.corner_num_nodes ** 2 + 2 * self.sum_to_corner * self.corner_num_nodes
		sum_corner_to_corner = sum_c1c3 + sum_c1c2 + sum_c1c4 + sum_c2c3 + sum_c2c4 + sum_c3c4
		total_sum = sums_within_corners + sum_within_middle + sum_centers_to_corners + sum_corner_to_corner
		return total_sum

def main():
	num_iter = int(input())
	A = list(map(int, input().split()))
	hc = city(A, num_iter)
	for i in range(num_iter):
		hc.run_iteration()
	print(hc.total_path_sums)
main()


mod = 10 ** 9 + 7
p = int(input())
arr = [int(x) for x in input().split()]
d = 0
x = 0
y = 0
n = 1
for i in range(p):
	a = arr[i]
	x = (4 * x + 2 * (2 * y * n + 2 * a * n ** 2) + 4 * (2 * y * n + 3 * a * n ** 2) + a + 4 * (y + a * n) + 4 * (y + 2 * a * n)) % mod
	y = (y + (y + 2 * a * n + d * n) + 2 * (y + 3 * a * n + d * n) + (d + a) + (d + 2 * a)) % mod
	n = (4 * n + 2) % mod
	d = (2 * d + 3 * a) % mod
print(x)


import sys, math
import itertools
N = int(input())
A = [int(i) for i in input().strip().split()]
Q = 1
S = 0
L = 0
D = 0
for n in range(0, N):
	new_Q = Q * 4 + 2
	add_Q = Q * 3 + 2
	S = (S * 4 + A[n] * math.floor(new_Q / 2) ** 2 + A[n] * 4 * Q * add_Q + 4 * L * add_Q) % 1000000007
	old_D = D
	D = (D * 2 + 3 * A[n]) % 1000000007
	L = (4 * L + 8 * Q * A[n] + D + 3 * Q * old_D) % 1000000007
	Q = new_Q % 1000000007
print(S % 1000000007)


MOD = 10 ** 9 + 7
input()
L = [int(i) for i in input().strip().split()]
n = 1
c = 0
d = 0
ans = 0
for l in L:
	ans *= 4
	ans += l
	midSum = (8 * c + 12 * l * n) % MOD
	edges = (12 * c + 16 * l * n) % MOD * n % MOD
	ans = (ans + midSum + edges) % MOD
	c = (4 * c + (8 * l + 3 * d) * n + 3 * l + 2 * d) % MOD
	n = (4 * n + 2) % MOD
	d = (d * 2 + 3 * l) % MOD
print(ans)


N = int(input())
A = [int(x) for x in input().strip().split()]
nb_of_nodes = 1
diagonal_distance = 0
total_distance_to_corner = 0
total_distance_to_each_other = 0
for i in range(N):
	intra_bloc_distance = total_distance_to_each_other
	inter_block_distance_1 = 2 * nb_of_nodes * total_distance_to_corner + 2 * A[i] * nb_of_nodes ** 2
	inter_block_distance_1 = inter_block_distance_1 % 1000000007
	inter_block_distance_2 = 2 * nb_of_nodes * total_distance_to_corner + 3 * A[i] * nb_of_nodes ** 2
	inter_block_distance_2 = inter_block_distance_2 % 1000000007
	new_nodes_to_all_distance = 2 * (4 * total_distance_to_corner + 6 * nb_of_nodes * A[i]) + A[i]
	total_distance_to_each_other = 4 * intra_bloc_distance + 2 * inter_block_distance_1 + 4 * inter_block_distance_2 + new_nodes_to_all_distance
	total_distance_to_each_other = total_distance_to_each_other % 1000000007
	block_to_corner_distance = total_distance_to_corner
	inter_block_to_corner_distance_1 = block_to_corner_distance + nb_of_nodes * (diagonal_distance + 2 * A[i])
	inter_block_to_corner_distance_1 = inter_block_to_corner_distance_1 % 1000000007
	inter_block_to_corner_distance_2 = block_to_corner_distance + nb_of_nodes * (diagonal_distance + 3 * A[i])
	inter_block_to_corner_distance_2 = inter_block_to_corner_distance_2 % 1000000007
	new_nodes_to_corner_distance = 2 * diagonal_distance + 3 * A[i]
	total_distance_to_corner = block_to_corner_distance + inter_block_to_corner_distance_1 + 2 * inter_block_to_corner_distance_2 + new_nodes_to_corner_distance
	total_distance_to_corner = total_distance_to_corner % 1000000007
	nb_of_nodes = 4 * nb_of_nodes + 2
	nb_of_nodes = nb_of_nodes % 1000000007
	diagonal_distance = 2 * diagonal_distance + 3 * A[i]
	diagonal_distance = diagonal_distance % 1000000007
print(total_distance_to_each_other)


times = int(input())
a = [int(x) for x in input().strip().split()]
mod = 1000000007
s = [0 for _ in range(times + 1)]
c = [0 for _ in range(times + 1)]
d = [0 for _ in range(times + 1)]
p = [1 for _ in range(times + 1)]
for n in range(times):
	p[n + 1] = (4 * p[n] + 2) % mod
	d[n + 1] = (2 * d[n] + 3 * a[n]) % mod
	c[n + 1] = (c[n] + (a[n] + d[n]) + (2 * a[n] + d[n]) + (p[n] * (2 * a[n] + d[n]) + c[n]) + 2 * (c[n] + p[n] * (3 * a[n] + d[n]))) % mod
	s[n + 1] = (4 * s[n] + 2 * (p[n] * (p[n] * 2 * a[n] + 2 * c[n])) + 4 * (p[n] * (p[n] * 3 * a[n] + 2 * c[n])) + 4 * (c[n] + p[n] * a[n] + c[n] + p[n] * 2 * a[n]) + a[n]) % mod
print(s[times] % mod)


n = int(input())
c = [1]
d = [0]
j = [0]
f = [0]
a = [int(k) for k in input().split(' ')]
for i in range(1, n + 1):
	c.append((4 * c[i - 1] + 2) % 1000000007)
	d.append((2 * d[i - 1] + 3 * a[i - 1]) % 1000000007)
	j.append((c[i - 1] * (8 * a[i - 1] + 3 * d[i - 1]) + 4 * j[i - 1] + 2 * d[i - 1] + 3 * a[i - 1]) % 1000000007)
	f.append((4 * f[i - 1] + a[i - 1] + 12 * j[i - 1] * c[i - 1] + 16 * a[i - 1] * c[i - 1] * c[i - 1] + 8 * j[i - 1] + 12 * c[i - 1] * a[i - 1]) % 1000000007)
print(f[n])


mod = 10 ** 9 + 7

def resolve(n, A):
	for i in range(1, len(A)):
		dp[i][3] = (4 * dp[i - 1][3] + 2) % mod
		dp[i][2] = (2 * dp[i - 1][2] + 3 * A[i]) % mod
		dp[i][1] = (dp[i - 1][1] + (dp[i - 1][1] * 3 + dp[i - 1][3] * (8 * A[i]) + 3 * A[i]) + (dp[i - 1][3] * 3 + 2) * dp[i - 1][2]) % mod
		dp[i][0] = (dp[i - 1][0] * 4 + 2 * (((dp[i - 1][1] + 3 * A[i] * dp[i - 1][3]) * dp[i - 1][3] + dp[i - 1][1] * dp[i - 1][3]) * 2 + (dp[i - 1][1] + 2 * A[i] * dp[i - 1][3]) * dp[i - 1][3] + dp[i - 1][1] * dp[i - 1][3]) + 2 * (2 * (dp[i - 1][1] * 2 + 3 * A[i] * dp[i - 1][3])) + A[i]) % mod
	print(dp[-1][0])
n = int(input())
A = [0]
A.extend(list(map(int, input().split())))
dp = [[0, 0, 0, 1] for i in range(n + 1)]
resolve(n, A)


k = int(input().strip())
A = [int(m) for m in input().strip().split()]
M = int(1000000000.0 + 7)
S = [0]
T = [0]
t = [0]
N = [1]
for i in range(1, k + 1):
	Si = 4 * S[i - 1] + 12 * N[i - 1] * (A[i - 1] + T[i - 1]) + 16 * N[i - 1] ** 2 * A[i - 1] + 8 * T[i - 1] + A[i - 1]
	ti = 2 * t[i - 1] + 3 * A[i - 1]
	Ti = T[i - 1] + (T[i - 1] + 2 * N[i - 1] * A[i - 1] + N[i - 1] * t[i - 1]) + 2 * (T[i - 1] + 3 * N[i - 1] * A[i - 1] + N[i - 1] * t[i - 1]) + 3 * A[i - 1] + 2 * t[i - 1]
	Ni = N[i - 1] * 4 + 2
	N.append(Ni % M)
	S.append(Si % M)
	t.append(ti % M)
	T.append(Ti % M)
print(S[-1])


(N, A) = (int(input()), [0] + [int(x) for x in input().split()])
mod = 1000000007
ans = _sum = d = 0
c = 1
for i in range(1, N + 1):
	ans = (4 * ans + 4 * _sum * (3 * c + 2) + (4 * (4 * c + 3) * c + 1) * A[i]) % mod
	_sum = ((c * 8 + 3) * A[i] + 4 * _sum + (3 * c + 2) * d) % mod
	c = (4 * c + 2) % mod
	d = (d * 2 + 3 * A[i]) % mod
print(ans)


MOD = 10 ** 9 + 7
n = int(input())
xs = list(map(int, input().split()))
s = 1
p = 0
l = 0
d = 0
for a in xs:
	new_s = (4 * s + 2) % MOD
	new_p = (4 * p + 12 * s * l + 16 * a * s * s + a + 12 * a * s + 8 * l) % MOD
	new_l = (4 * l + 2 * d + 3 * a + 3 * s * d + 8 * a * s) % MOD
	new_d = (3 * a + 2 * d) % MOD
	(s, p, l, d) = (new_s, new_p, new_l, new_d)
print(p)


n = int(input())
array = [int(i) for i in input().split()]
assert 1 <= n <= 10 ** 6
assert all([1 <= x <= 9 for x in array])
M = 10 ** 9 + 7
(curSum, curSumFromVertex, curVertexCount, height) = (0, 0, 1, 0)
for a in array:
	newYSum = (curSumFromVertex + a * curVertexCount) * 2 + (curSumFromVertex + 2 * a * curVertexCount) * 2 + a
	newSumFromVertex = curSumFromVertex + (curSumFromVertex + (height + 2 * a) * curVertexCount) + 2 * (curSumFromVertex + (height + 3 * a) * curVertexCount) + height + a + height + 2 * a
	newSum1 = 2 * (2 * curSumFromVertex * curVertexCount + 2 * a * curVertexCount * curVertexCount)
	newSum2 = 4 * (2 * curSumFromVertex * curVertexCount + 3 * a * curVertexCount * curVertexCount)
	curSum = newSum1 + newSum2 + newYSum * 2 - a + curSum * 4
	curSumFromVertex = newSumFromVertex
	height = height * 2 + 3 * a
	curVertexCount = curVertexCount * 4 + 2
	curSum %= M
	curSumFromVertex %= M
	curVertexCount %= M
	height %= M
print(curSum)


n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
(x, y, z, d) = (29 * a[0], 11 * a[0], 6, 3 * a[0])
for i in range(n - 1):
	(x, y, z, d) = ((4 * x + 29 * a[i + 1] + 20 * y + 44 * (z - 1) * a[i + 1] + 16 * (z - 1) ** 2 * a[i + 1] + 12 * (z - 1) * y) % 1000000007, (y + (3 * z + 2) * d + 11 * a[i + 1] + 8 * (z - 1) * a[i + 1] + 3 * y) % 1000000007, (4 * z + 2) % 1000000007, (d * 2 + a[i + 1] * 3) % 1000000007)
print(x)


N = int(input())
As = tuple(map(int, input().strip().split()))
MOD = 10 ** 9 + 7
(n, e, f, d) = (1, 0, 0, 0)
for a in As:
	nf = 4 * f + (12 * n + 8) * e + 4 * n * (3 * n + 2) * a + a * (2 * n + 1) ** 2
	ne = 4 * e + (3 * n + 2) * d + (8 * n + 3) * a
	nd = 2 * d + 3 * a
	nn = 4 * n + 2
	(n, e, f, d) = map(lambda x: x % MOD, (nn, ne, nf, nd))
print(f)


import sys
p = 1000000007
T = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
n = 6
d = 3 * A[0] % p
b = 11 * A[0] % p
i = 29 * A[0] % p
for t in range(1, T):
	i = (4 * i % p + 12 * b % p * n % p + n * n % p * (A[t] * 16 % p) % p + 8 * b % p + 12 * n % p * A[t] % p + A[t]) % p
	b = (4 * b % p + n * ((8 * A[t] % p + 3 * d % p) % p) % p + 3 * A[t] % p + 2 * d % p) % p
	d = (2 * d % p + 3 * A[t] % p) % p
	n = (4 * n + 2) % p
print(i)


def mod_func(i):
	return i % 1000000007

def next_C(prev_c):
	return mod_func(4 * prev_c + 2)

def next_K(prev_k, a):
	return mod_func(2 * prev_k + 3 * a)

def next_P(prev_p, prev_k, prev_c, a):
	return mod_func(mod_func(prev_p + prev_k * 2 + a * 3) + mod_func(mod_func(mod_func(prev_k + 2 * a) * prev_c) + prev_p) + mod_func(mod_func(mod_func(mod_func(prev_k + 3 * a) * prev_c) + prev_p) * 2))

def next_T(prev_t, prev_p, prev_c, a):
	return mod_func(mod_func(4 * prev_t) + mod_func(mod_func(2 * mod_func(prev_p * prev_c) + prev_c * prev_c * 2 * a) * 2) + mod_func(mod_func(2 * mod_func(prev_p * prev_c) + mod_func(prev_c * prev_c) * 3 * a) * 4) + mod_func(mod_func(prev_p + mod_func(a * prev_c)) * 4) + mod_func(mod_func(prev_p + mod_func(2 * a * prev_c)) * 4) + a)

def main():
	mod = 1000000007
	C = [1]
	K = [0]
	P = [0]
	T = [0]
	n = int(input(''))
	A = list(map(int, input('').split(' ')))
	index = 0
	for a in A:
		prev_c = C[index]
		prev_k = K[index]
		prev_p = P[index]
		prev_t = T[index]
		C.append(next_C(prev_c))
		K.append(next_K(prev_k, a))
		P.append(next_P(prev_p, prev_k, prev_c, a))
		T.append(next_T(prev_t, prev_p, prev_c, a))
		index += 1
	print(T[-1])
main()


Q = 0
C = 0
J = 0
S = 1
T = 0
n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
for i in range(n):
	A = a[i]
	new_t = (2 * T + 3 * A) % MOD
	new_s = (4 * S + 2) % MOD
	new_j = (8 * A * S + 4 * J + 3 * A + 2 * T + 3 * S * T) % MOD
	new_q = (8 * A * S ** 2 + 6 * J * S + 3 * A * S + 2 * J + 4 * Q + 2 * C) % MOD
	new_c = (4 * J + 6 * A * S + A) % MOD
	T = new_t
	S = new_s
	J = new_j
	Q = new_q
	C = new_c
print((2 * Q + C) % MOD)


mod = 1000000007
(x, y, z, n) = (0, 0, 0, 1)
num_q = int(input())
Q = [int(a) for a in input().split()]
for q in Q:
	nq = n * q % mod
	nnq = nq * n % mod
	ny = n * y % mod
	x = (4 * x + 16 * nnq + 12 * nq + 12 * ny + 8 * y + q) % mod
	y = (y + n * (z + 2 * q) + y + 2 * (n * (z + 3 * q) + y) + (z + q) + (z + 2 * q)) % mod
	z = (2 * z + 3 * q) % mod
	n = (4 * n + 2) % mod
print(x)


n = int(input())
ls = [int(x) for x in input().split()]
mod = 10 ** 9 + 7
count = 1
longdist = 0
sumdist = 0
res = 0
for (i, l) in enumerate(ls):
	res = (res * 4 + count ** 2 * 16 * l + count * 12 * l + l + 20 * pow(4, i, mod) * sumdist) % mod
	sumdist = (sumdist * 4 + (3 * l + 2 * longdist) + count * (8 * l + 3 * longdist)) % mod
	count = (count * 4 + 2) % mod
	longdist = (longdist * 2 + 3 * l) % mod
print(res)


N = int(input())
id = 0
corner_distance = 0
H = 1
total = 0
A = input().split()
for i in range(N):
	ai = int(A[i])
	total = (4 * total + (H * id + ai * 3 * H * H + id * H) * 4 + (H * id + ai * 2 * H * H + id * H) * 2 + (H * ai + id) * 4 + (H * (2 * ai) + id) * 4 + ai) % 1000000007
	id = (4 * id + 3 * H * (3 * ai + corner_distance) - H * ai + 3 * ai + 2 * corner_distance) % 1000000007
	corner_distance = (2 * corner_distance + 3 * ai) % 1000000007
	H = (4 * H + 2) % 1000000007
	N -= 1
print(total % 1000000007)


N = int(input())
elens = list(map(int, input().split()))
MOD = 1000000007
diaglen = 0
suml2xtrm = 0
sum2wisel = 0
numel = 1
for i in range(N):
	elen = elens[i]
	new_diaglen = (diaglen * 2 + 3 * elen) % MOD
	new_suml2xtrm = (suml2xtrm + (suml2xtrm + (diaglen + 2 * elen) * numel) + (suml2xtrm + (diaglen + 3 * elen) * numel) * 2 + diaglen * 2 + 3 * elen) % MOD
	new_sum2wisel = (sum2wisel * 4 + (2 * suml2xtrm * numel + 2 * elen * numel * numel) * 2 + (2 * suml2xtrm * numel + 3 * elen * numel * numel) * 4 + (suml2xtrm + 1 * elen * numel) * 4 + (suml2xtrm + 2 * elen * numel) * 4 + 1 * elen) % MOD
	new_numel = (numel * 4 + 2) % MOD
	(diaglen, suml2xtrm, sum2wisel, numel) = (new_diaglen, new_suml2xtrm, new_sum2wisel, new_numel)
print(sum2wisel)


n = int(input())
steps = map(int, input().split())
M = 1000000007
junction = [0]
diagonal = [0]
node_count = [1]
node_to_node = [0]
i = 0
for dist in steps:
	i += 1
	diagonal.append(diagonal[i - 1] * 2 + 3 * dist)
	junction.append(junction[i - 1])
	junction[i] += 2 * (junction[i - 1] + node_count[i - 1] * 3 * dist + node_count[i - 1] * diagonal[i - 1])
	junction[i] += junction[i - 1] + node_count[i - 1] * 2 * dist + node_count[i - 1] * diagonal[i - 1]
	junction[i] += diagonal[i - 1] + dist
	junction[i] += diagonal[i - 1] + 2 * dist
	node_to_node.append(4 * node_to_node[i - 1])
	node_to_node[i] += 4 * (node_count[i - 1] * node_count[i - 1] * 3 * dist + node_count[i - 1] * 2 * junction[i - 1])
	node_to_node[i] += 2 * (node_count[i - 1] * node_count[i - 1] * 2 * dist + node_count[i - 1] * 2 * junction[i - 1])
	node_to_node[i] += 4 * (dist * node_count[i - 1] + junction[i - 1])
	node_to_node[i] += 4 * (2 * dist * node_count[i - 1] + junction[i - 1])
	node_to_node[i] += dist
	node_count.append(node_count[i - 1] * 4 + 2)
	diagonal[i] %= M
	junction[i] %= M
	node_to_node[i] %= M
	node_count[i] %= M
print(node_to_node[i])


N = int(input())
A = [int(a) for a in input().split(' ')]
T = [0]
E = [0]
D = [0]
K = [1]
mu = 10 ** 9 + 7
for n in range(N):
	T.append((4 * T[-1] + 2 * (E[-1] * K[-1] + 2 * A[n] * K[-1] ** 2 + E[-1] * K[-1]) + 4 * (E[-1] * K[-1] + 3 * A[n] * K[-1] ** 2 + E[-1] * K[-1]) + 4 * (K[-1] * A[n] + E[-1]) + 4 * (K[-1] * 2 * A[n] + E[-1]) + A[n]) % mu)
	E.append((2 * (E[-1] + 3 * A[n] * K[-1] + K[-1] * D[-1]) + (E[-1] + 2 * A[n] * K[-1] + K[-1] * D[-1]) + E[-1] + 1 * A[n] + D[-1] + 2 * A[n] + D[-1]) % mu)
	K.append((4 * K[-1] + 2) % mu)
	D.append((2 * D[-1] + 3 * A[n]) % mu)
print(T[-1])


modulo = 10 ** 9 + 7
n = int(input())
a = [int(i) for i in input().split()]
ts = 0
sc = 0
p = 1
scc = 0
for i in range(n):
	A = a[i]
	ts = (4 * ts + 4 * (2 * sc + 3 * p * A) + 2 * (2 * A * p * p + 2 * p * sc) + 4 * (3 * A * p * p + 2 * p * sc) + A) % modulo
	sc = (sc + 2 * scc + 3 * A + p * (scc + 2 * A) + sc + 2 * (p * (scc + 3 * A) + sc)) % modulo
	p = (4 * p + 2) % modulo
	scc = (2 * scc + 3 * A) % modulo
print(ts)


from collections import deque

def parseInput(f):
	return [f(x) for x in input().split()]
MOD = 1000000007
n = int(input())
a = parseInput(int)
nv = 1
sd = 0
dtc = 0
diam = 0
for ne in a:
	nnv = nv * 4 + 2
	nsd = 4 * sd + 4 * dtc * (2 + 3 * nv % MOD) % MOD + 4 * ne * nv % MOD * (nv * 3 + 2) % MOD + ne * (2 * nv + 1) % MOD * (2 * nv + 1) % MOD
	ndtc = 4 * dtc + 8 * ne * nv % MOD + 3 * ne + (3 * nv + 2) * diam % MOD
	ndiam = 2 * diam + 3 * ne
	nv = nnv % MOD
	sd = nsd % MOD
	dtc = ndtc % MOD
	diam = ndiam % MOD
print(sd)


n = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
totalDist = 0
totalNum = 1
totalAng = 0
fullLen = 0
for i in A:
	newTotalNum = 4 * totalNum + 2
	newFullLen = 2 * fullLen + 3 * i
	newTotalAng = 4 * totalAng + totalNum * (2 * i + fullLen) + 2 * totalNum * (3 * i + fullLen) + 2 * fullLen + 3 * i
	newTotalDist = 4 * totalDist + 4 * i * totalNum * (2 + 3 * totalNum) + i * (2 * totalNum + 1) ** 2 + 4 * 3 * totalNum * totalAng + 4 * totalAng * 2
	totalDist = newTotalDist % MOD
	totalAng = newTotalAng % MOD
	fullLen = newFullLen % MOD
	totalNum = newTotalNum % MOD
print(totalDist)


n = int(input())
A = list(map(int, filter(None, input().split(' '))))
E = [0] * (n + 1)
X = [0] * (n + 1)
D = [0] * (n + 1)
N = [0] * (n + 1)
E[0] = 0
N[0] = 1
X[0] = 0
D[0] = 0
mod = 1000000007
for i in range(1, n + 1):
	X[i] = (4 * X[i - 1] + (2 * (D[i - 1] + 3 * A[i - 1]) + D[i - 1] + 2 * A[i - 1]) * N[i - 1] + (2 * D[i - 1] + 3 * A[i - 1])) % mod
	D[i] = (2 * D[i - 1] + 3 * A[i - 1]) % mod
	N[i] = (4 * N[i - 1] + 2) % mod
	E[i] = (4 * E[i - 1] + A[i - 1] * (12 * N[i - 1] * N[i - 1] + 8 * N[i - 1]) + A[i - 1] * (4 * N[i - 1] * N[i - 1] + (4 * N[i - 1] + 1)) + 4 * (X[i - 1] * (3 * N[i - 1] + 2))) % mod
print(E[n])


N = int(input())
A = [int(x) for x in input().split()]
mod = 1000000007
sum_pair_dist = 0
sum_corner_dist = 0
corner_corner_dist = 0
node_count = 1
for side_len in A:
	sum_pair_dist = (4 * sum_pair_dist + ((16 * node_count + 12) * node_count + 1) * side_len + (12 * node_count + 8) * sum_corner_dist) % mod
	sum_corner_dist = (4 * sum_corner_dist + (8 * node_count + 3) * side_len + (3 * node_count + 2) * corner_corner_dist) % mod
	corner_corner_dist = (2 * corner_corner_dist + 3 * side_len) % mod
	node_count = (4 * node_count + 2) % mod
print(sum_pair_dist)


n = int(input())
array = [int(i) for i in input().split()]
assert 1 <= n <= 10 ** 6
assert all([1 <= x <= 9 for x in array])
M = 10 ** 9 + 7
(curSum, curSumFromVertex, curVertexCount, height) = (0, 0, 1, 0)
for a in array:
	newYSum = (curSumFromVertex + a * curVertexCount) * 2 + (curSumFromVertex + 2 * a * curVertexCount) * 2 + a
	newSumFromVertex = curSumFromVertex + (curSumFromVertex + (height + 2 * a) * curVertexCount) + 2 * (curSumFromVertex + (height + 3 * a) * curVertexCount) + height + a + height + 2 * a
	newSum1 = 2 * (2 * curSumFromVertex * curVertexCount + 2 * a * curVertexCount * curVertexCount)
	newSum2 = 4 * (2 * curSumFromVertex * curVertexCount + 3 * a * curVertexCount * curVertexCount)
	curSum = newSum1 + newSum2 + newYSum * 2 - a + curSum * 4
	curSumFromVertex = newSumFromVertex
	height = height * 2 + 3 * a
	curVertexCount = curVertexCount * 4 + 2
	curSum %= M
	curSumFromVertex %= M
	curVertexCount %= M
	height %= M
print(curSum)


import os
import sys

def hackerrankCity(A):
	a = [0] + A
	m = 1000000007
	n = len(A)
	d = []
	mysum = []
	diag = []
	num = []
	diag.append(0)
	num.append(1)
	mysum.append(0)
	d.append(0)
	for i in range(1, n + 1):
		num.append((num[i - 1] * 4 + 2) % m)
		diag.append((2 * diag[i - 1] + 3 * a[i]) % m)
		d1 = d[i - 1]
		d2 = diag[i - 1] + a[i] + (diag[i - 1] + 2 * a[i])
		d3 = (diag[i - 1] + 2 * a[i]) * num[i - 1] + d[i - 1]
		d4 = 2 * ((diag[i - 1] + 3 * a[i]) * num[i - 1] + d[i - 1])
		d.append((d1 + d2 + d3 + d4) % m)
		s1 = 4 * mysum[i - 1]
		s2 = 2 * d[i - 1] * num[i - 1] + num[i - 1] * num[i - 1] * 2 * a[i]
		s3 = 2 * (2 * d[i - 1] * num[i - 1] + num[i - 1] * num[i - 1] * 3 * a[i])
		s4 = 4 * (s2 + s3)
		s5 = 4 * d[i - 1] + 6 * num[i - 1] * a[i]
		s7 = 2 * s5
		s8 = s1 + s7 + s4 // 2 + a[i]
		mysum.append(s8 % m)
	return mysum[n] % m
A_count = int(input())
A = list(map(int, input().rstrip().split()))
result = hackerrankCity(A)
print(str(result) + '\n')


M = 10 ** 9 + 7

def modular_inv(n):
	res = 1
	while n > 1:
		res = res * (M - M // n) % M
		n = M % n
	return res
n = int(input())
distances = list(map(int, input().split()))
nodes = 1
avg = total = diagonal = 0
for (i, dist) in enumerate(distances):
	nodes2 = pow(nodes, 2, M)
	total = (4 * nodes * (avg + dist) + 4 * nodes * (avg + 2 * dist) + 2 * nodes2 * (2 * avg + 2 * dist) + 4 * nodes2 * (2 * avg + 3 * dist) + 4 * total + dist) % M
	avg = 2 * diagonal + 3 * dist + (3 * diagonal + 8 * dist + 4 * avg) * nodes
	diagonal = (2 * diagonal + 3 * dist) % M
	nodes = (4 * nodes + 2) % M
	avg = avg * modular_inv(nodes) % M
print(round(total) % M)


levels = int(input())
a = [int(x) for x in input().split()]
d = [0 for x in range(levels + 1)]
e = [0 for x in range(levels + 1)]
s = [0 for x in range(levels + 1)]
c = [0 for x in range(levels + 1)]
d[0] = 1
mod = 1000000000 + 7
for x in range(1, levels + 1):
	a0 = a[x - 1]
	d0 = d[x - 1]
	e0 = e[x - 1]
	s0 = s[x - 1]
	c0 = c[x - 1]
	e[x] = (2 * e0 + 3 * a0) % mod
	d[x] = (d0 * 4 + 2) % mod
	d1 = (3 * d0 + 2) % mod
	d2 = (8 * d0 + 3) % mod
	d3 = (2 * d0 + 1) % mod
	c[x] = (c0 * 4 % mod + d1 * e0 % mod + a0 * d2 % mod) % mod
	s[x] = (4 * s0 % mod + c0 * d1 * 4 % mod + a0 * d3 * d3 % mod + a0 * d0 * d1 * 4 % mod) % mod
print(s[levels])


from functools import reduce
(n, M) = (input(), 10 ** 9 + 7)
print(reduce(lambda p, a: (((3 * p[1] + 2) * p[3] * 4 + (2 * p[1] + 1) ** 2 * a + p[1] * (3 * p[1] + 2) * 4 * a + 4 * p[0]) % M, (4 * p[1] + 2) % M, 2 * (p[2] + a) % M, (p[3] * 4 + (p[2] + p[4] + 3 * a) * 2 * p[1] + (p[2] + p[4] + 2 * a) * p[1] + 2 * (p[2] + p[4]) + 3 * a) % M, (2 * p[4] + a) % M), [int(x) for x in input().split(' ')], (0, 1, 0, 0, 0))[0])


M = 1000000007
d = n = c = s = 0
input()
for a in map(int, input().split()):
	d2 = 2 * d + 3 * a
	n2 = 4 * n + 5
	c2 = 4 * c + 3 * n * d + 8 * n * a + 5 * d + 11 * a
	s2 = 4 * s + 12 * c * n + 16 * a * n ** 2 + 20 * c + 44 * a * n + 29 * a
	(d, n, c, s) = (d2 % M, n2 % M, c2 % M, s2 % M)
print(s)


n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


import os
import sys
n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


import os
import sys
n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


import os
import sys
n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


P = 10 ** 9 + 7

def main():
	N = int(input())
	A = list(map(int, input().split()))
	D = [0] * (N + 1)
	F = [0] * (N + 1)
	S = [1] * (N + 1)
	X = [0] * (N + 1)
	for n in range(1, N + 1):
		S[n] = 4 * S[n - 1] + 2
		S[n] %= P
		X[n] = 2 * X[n - 1] + 3 * A[n - 1]
		X[n] %= P
		F[n] = F[n - 1]
		F[n] += F[n - 1] + (2 * A[n - 1] + X[n - 1]) * S[n - 1]
		F[n] += 2 * (F[n - 1] + (3 * A[n - 1] + X[n - 1]) * S[n - 1])
		F[n] += X[n - 1] + A[n - 1]
		F[n] += X[n - 1] + 2 * A[n - 1]
		F[n] %= P
		D[n] = 4 * D[n - 1]
		D[n] += 4 * (2 * F[n - 1] * S[n - 1] + 3 * A[n - 1] * S[n - 1] ** 2)
		D[n] += 2 * (2 * F[n - 1] * S[n - 1] + 2 * A[n - 1] * S[n - 1] ** 2)
		D[n] += 4 * (F[n - 1] + A[n - 1] * S[n - 1])
		D[n] += 4 * (F[n - 1] + 2 * A[n - 1] * S[n - 1])
		D[n] += A[n - 1]
		D[n] %= P
	print(D[N])
main()


n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


n = int(input())
c = [1]
d = [0]
j = [0]
f = [0]
a = [int(k) for k in input().split(' ')]
for i in range(1, n + 1):
	c.append((4 * c[i - 1] + 2) % 1000000007)
	d.append((2 * d[i - 1] + 3 * a[i - 1]) % 1000000007)
	j.append((c[i - 1] * (8 * a[i - 1] + 3 * d[i - 1]) + 4 * j[i - 1] + 2 * d[i - 1] + 3 * a[i - 1]) % 1000000007)
	f.append((4 * f[i - 1] + a[i - 1] + 12 * j[i - 1] * c[i - 1] + 16 * a[i - 1] * c[i - 1] * c[i - 1] + 8 * j[i - 1] + 12 * c[i - 1] * a[i - 1]) % 1000000007)
print(f[n])


n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


def compute(A):
	S = 1
	D = 0
	E = 0
	F = 0
	M = 10 ** 9 + 7
	for n in range(1, len(A) + 1):
		Sn = 4 * S + 2
		Dn = 2 * D + 3 * A[n - 1]
		En = 4 * E + (3 * S + 2) * D + (3 + 8 * S) * A[n - 1]
		Fn = 4 * F + (12 * S + 8) * E + (12 * S + 16 * S * S + 1) * A[n - 1]
		S = Sn % M
		D = Dn % M
		E = En % M
		F = Fn % M
	return F
n = int(input())
A = [int(x) for x in input().split()]
print(compute(A))


n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


N = int(input())
A = [int(x) for x in input().split()]
S = 29 * A[0]
L = 11 * A[0]
LL = 3 * A[0]
M = 1000000007
n = 6
for i in range(1, N):
	na = n * A[i]
	na2 = na + na
	L2 = (L + L) % M
	na2L = (na2 + L2) % M
	S = (4 * (S + na + na2L + n * (na2L + na)) + 2 * n * na2L + A[i]) % M
	L = (L2 + 2 * (3 * na + n * LL) + na2L + n * LL + 3 * A[i] + 2 * LL) % M
	LL = (LL + LL + 3 * A[i]) % M
	n = (4 * n + 2) % M
print(S)


n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


import os
import sys

def prec(p):
	return (p - 2) // 4
N = int(input())
A = list(map(int, input().rstrip().split()))
p = 1
s = 0
diag = 0
h = 0
m = 10 ** 9 + 7
for n in A:
	p1 = (p % m * 4 + 2) % m
	h = (h * 4 % m + n % m + s * (p1 - p) % m * 4 % m + 16 * n * p ** 2 % m % m + p * 12 * n % m) % m
	s = s * 4 % m + p * 8 * n % m + diag * (p1 - p) % m + 3 * n
	diag = (diag * 2 + 3 * n) % m
	p = p1
print(h % m)


n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)


import sys
inp = sys.stdin
n = int(inp.readline().strip())
lengths = list(map(int, inp.readline().strip().split(' ')))
f = 0
g = 0
h = 0
m = 1
for a in lengths:
	f = (4 * g * (3 * m + 2) + 4 * f + 16 * a * m * m + 12 * a * m + a) % 1000000007
	g = (4 * g + m * (3 * h + 8 * a) + 2 * h + 3 * a) % 1000000007
	h = (2 * h + 3 * a) % 1000000007
	m = (4 * m + 2) % 1000000007
print(f)


n = int(input())
valueIn = list(map(int, input().split()))
numArr = [1]
pointArr = [0]
res = [0]
distance = 0
for i in range(1, n + 1):
	a = valueIn[i - 1]
	num = numArr[i - 1]
	pointer = pointArr[i - 1]
	numArr.append((numArr[i - 1] * 4 + 2) % 1000000007)
	pointArr.append((pointer * 4 + (2 + 3 * num) * distance + a * (3 + 6 * num + 2 * num)) % 1000000007)
	res.append((res[i - 1] * 4 + pointer * (numArr[i] - num) * 4 + (6 * num * 2 + 1) * a + num * num * 16 * a) % 1000000007)
	distance = (distance * 2 + 3 * a) % 1000000007
print(res[-1] % 1000000007)