Karen has just arrived at school, and she has a math test today! [Image] 

The test is about basic addition and subtraction. Unfortunately, the teachers were too busy writing tasks for Codeforces rounds, and had no time to make an actual test. So, they just put one question in the test that is worth all the points.

There are n integers written on a row. Karen must alternately add and subtract each pair of adjacent integers, and write down the sums or differences on the next row. She must repeat this process on the values on the next row, and so on, until only one integer remains. The first operation should be addition.

Note that, if she ended the previous row by adding the integers, she should start the next row by subtracting, and vice versa.

The teachers will simply look at the last integer, and then if it is correct, Karen gets a perfect score, otherwise, she gets a zero for the test.

Karen has studied well for this test, but she is scared that she might make a mistake somewhere and it will cause her final answer to be wrong. If the process is followed, what number can she expect to be written on the last row?

Since this number can be quite large, output only the non-negative remainder after dividing it by 10^9 + 7.


-----Input-----

The first line of input contains a single integer n (1 ≤ n ≤ 200000), the number of numbers written on the first row.

The next line contains n integers. Specifically, the i-th one among these is a_{i} (1 ≤ a_{i} ≤ 10^9), the i-th number on the first row.


-----Output-----

Output a single integer on a line by itself, the number on the final row after performing the process above.

Since this number can be quite large, print only the non-negative remainder after dividing it by 10^9 + 7.


-----Examples-----
Input
5
3 6 9 12 15

Output
36

Input
4
3 7 5 2

Output
1000000006



-----Note-----

In the first test case, the numbers written on the first row are 3, 6, 9, 12 and 15.

Karen performs the operations as follows: [Image] 

The non-negative remainder after dividing the final number by 10^9 + 7 is still 36, so this is the correct output.

In the second test case, the numbers written on the first row are 3, 7, 5 and 2.

Karen performs the operations as follows: [Image] 

The non-negative remainder after dividing the final number by 10^9 + 7 is 10^9 + 6, so this is the correct output.

Difficulty: HARD
Tags: Complete search

Combinatorics

Mathematics

Constructive algorithms
Skill types: Complete search

Starter code:

Solutions:
from sys import exit
n = int(input())
a = [int(i) for i in input().split()]
if n == 1:
	print(a[0])
	exit(0)
mod = 1000000007
f = [0] * (n + 1)
f[0] = 1
for i in range(1, n + 1):
	f[i] = f[i - 1] * i % mod

def f_pow(a, k):
	if k == 0:
		return 1
	if k % 2 == 1:
		return f_pow(a, k - 1) * a % mod
	else:
		return f_pow(a * a % mod, k // 2) % mod

def c(n, k):
	d = f[k] * f[n - k] % mod
	return f[n] * f_pow(d, mod - 2) % mod
oper = 1
while not (oper and n % 2 == 0):
	for i in range(n - 1):
		a[i] = a[i] + oper * a[i + 1]
		oper *= -1
	n -= 1
oper *= 1 if n // 2 % 2 != 0 else -1
sm1 = 0
sm2 = 0
for i in range(n):
	if i % 2 == 0:
		sm1 = (sm1 + c(n // 2 - 1, i // 2) * a[i]) % mod
	else:
		sm2 = (sm2 + c(n // 2 - 1, i // 2) * a[i]) % mod
print((sm1 + oper * sm2) % mod)


import sys

def CreateFact(n, mod):
	cant = n + 1
	factorials = [1] * cant
	for x in range(1, cant):
		val = factorials[x - 1] * x % mod
		factorials[x] = val
	inv_factorial = [1] * cant
	inv_factorial[n] = pow(factorials[-1], mod - 2, mod)
	for x in reversed(range(0, n)):
		val = inv_factorial[x + 1] * (x + 1) % mod
		inv_factorial[x] = val
	return (factorials, inv_factorial)

def CalculateNPairsCoef(n, mod):
	(factorial, inv_factorial) = CreateFact(n, mod)
	coef = [1] * n
	middle = int((n + 1) / 2)
	last = n - 1
	for x in range(1, middle):
		o = factorial[n - 1] * inv_factorial[n - 1 - x] % mod * inv_factorial[x] % mod
		coef[x] = o
		coef[last - x] = o
	return coef

def KarenAdTest():
	n = int(sys.stdin.readline())
	line = sys.stdin.readline().split()
	i = 0
	while i < n:
		x = int(line[i])
		line[i] = x
		i += 1
	mod = 1000000007
	if n == 1:
		val = line[0] % mod
		print(val)
		return
	if n == 2:
		val = (line[0] + line[1]) % mod
		print(val)
		return
	if n == 3:
		val = (line[0] + 2 * line[1] - line[2]) % mod
		print(val)
		return
	if n == 4:
		val = (line[0] - line[1] + line[2] - line[3]) % mod
		print(val)
		return
	if n == 5:
		val = (line[0] + 2 * line[2] + line[4]) % mod
		print(val)
		return
	coefi = [1] * n
	if n % 2 == 0:
		m = int(n / 2)
		c = CalculateNPairsCoef(m, mod)
		pos = 0
		if n % 4 == 0:
			for x in range(0, m):
				coefi[pos] = c[x]
				pos += 1
				coefi[pos] = -c[x]
				pos += 1
		else:
			for x in range(0, m):
				coefi[pos] = c[x]
				pos += 1
				coefi[pos] = c[x]
				pos += 1
	else:
		sr = n - 1
		m = int(sr / 2)
		c = CalculateNPairsCoef(m, mod)
		co = [1] * sr
		pos = 2
		for x in range(1, m):
			co[pos] = c[x]
			pos += 1
			co[pos] = c[x]
			pos += 1
		if n % 4 == 1:
			coefi = [0] * n
			coefi[0] = coefi[n - 1] = 1
			for x in range(2, sr, 2):
				coefi[x] = co[x - 1] + co[x]
		else:
			for x in range(2, sr, 2):
				coefi[x] = -co[x - 1] + co[x]
			for x in range(1, sr, 2):
				coefi[x] = co[x - 1] + co[x]
			coefi[sr] = -1
	res = 0
	for x in range(0, n):
		res += coefi[x] * line[x] % mod
	res = int(res % mod)
	print(res)
KarenAdTest()


import math

def make_nCr_mod(max_n=2 * 10 ** 5 + 100, mod=10 ** 9 + 7):
	(fact, inv_fact) = ([0] * (max_n + 1), [0] * (max_n + 1))
	fact[0] = 1
	for i in range(max_n):
		fact[i + 1] = fact[i] * (i + 1) % mod
	inv_fact[-1] = pow(fact[-1], mod - 2, mod)
	for i in reversed(range(max_n)):
		inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

	def nCr_mod(n, r):
		res = 1
		while n or r:
			(a, b) = (n % mod, r % mod)
			if a < b:
				return 0
			res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
			n //= mod
			r //= mod
		return res
	return nCr_mod
nCr_mod = make_nCr_mod()
MODULUS = 10 ** 9 + 7
input()
A = input().split(' ')
A = list(map(int, A))
if len(A) == 1:
	print(A[0])
	exit(0)
if len(A) % 2 == 1:
	new_A = []
	next_plus = True
	for i in range(len(A) - 1):
		if next_plus:
			new_A += [A[i] + A[i + 1]]
		else:
			new_A += [A[i] - A[i + 1]]
		next_plus = not next_plus
	A = new_A
if len(A) % 4 == 2:
	new_A = []
	for i in range(len(A) // 2):
		new_A += [A[2 * i] + A[2 * i + 1]]
	A = new_A
else:
	new_A = []
	for i in range(len(A) // 2):
		new_A += [A[2 * i] - A[2 * i + 1]]
	A = new_A
N = len(A) - 1
ret = 0
for i in range(N + 1):
	ret += A[i] * nCr_mod(N, i)
	ret = ret % MODULUS
print(ret)


from sys import exit
from typing import List
MOD = 10 ** 9 + 7

def mod_inv(n: int) -> int:
	return pow(n, MOD - 2, MOD)

def tri_sum(row: List[int]) -> int:
	pascal_row = [1]
	for i in range(1, len(row)):
		last = pascal_row[-1]
		curr = last * (len(row) - i) * mod_inv(i) % MOD
		pascal_row.append(curr)
	total = 0
	for (contrib, val) in zip(pascal_row, row):
		total = (total + contrib * val) % MOD
	return total
row_len = int(input())
row = [int(i) for i in input().split()]
if len(row) != row_len:
	raise ValueError(f'the lengths {row_len} and {len(row)} are different so uh yeah')
if len(row) == 1:
	print(row[0])
	exit()
if row_len % 2 == 1:
	row_len -= 1
	new_row = []
	for i in range(row_len):
		new_row.append(row[i] + row[i + 1] if i % 2 == 0 else row[i] - row[i + 1])
	row = new_row
alt_rows = [[], []]
for (i, v) in enumerate(row):
	alt_rows[i % 2].append(v)
first = tri_sum(alt_rows[0])
second = tri_sum(alt_rows[1])
ans = (first + second if (row_len - 1) * row_len // 2 % 2 == 1 else first - second) % MOD
print(ans)


from sys import stdin, stdout

def main():
	N = 400005
	MOD = 10 ** 9 + 7
	fact = [1] + [i + 1 for i in range(N)]
	for i in range(1, N + 1):
		fact[i] *= fact[i - 1]
		fact[i] %= MOD

	def inv(n):
		return pow(n, MOD - 2, MOD)

	def simplex(n, k):
		if n == 0:
			return 1
		if k == 0:
			return 0
		return fact[n + k - 1] * inv(fact[n]) * inv(fact[k - 1]) % MOD

	def F1(z, i):
		if z == 1:
			return 1
		if z % 4 == 2:
			x = z // 4 * 2
			j = i % 4
			if j == 0:
				return simplex(x, i // 4 * 2 + 1)
			elif j == 1:
				return simplex(x, i // 4 * 2 + 1) * 2 % MOD
			elif j == 2:
				return MOD - simplex(x, i // 4 * 2 + 2)
			else:
				return 0
		elif z % 4 == 0:
			if i == 0:
				return MOD - 1
			if i == 1:
				return 0
			i -= 2
			x = z // 4 * 2 - 1
			j = i % 4
			if j == 0:
				return simplex(x, i // 4 * 2 + 2)
			elif j == 1:
				return simplex(x, i // 4 * 2 + 2) * 2 % MOD
			elif j == 2:
				return MOD - simplex(x, i // 4 * 2 + 3)
			else:
				return 0
		elif z % 4 == 3:
			if i == 0:
				return MOD - 1
			i -= 1
			x = z // 4 * 2 + 1
			y = z // 4 * 2 - 1
			j = i % 4
			if j % 4 == 0:
				return simplex(x, i // 4 * 2 + 1)
			elif j % 4 == 1 or j % 4 == 2:
				return simplex(x, i // 4 * 2 + 2)
			else:
				z1 = 0 if y < 0 else simplex(y, i // 4 * 2 + 3)
				ans = simplex(x, i // 4 * 2 + 1) - z1
				if ans < 0:
					ans += MOD
				return ans
		else:
			if i < 2:
				return 1
			if i == 2:
				return MOD - (z // 4 * 2 - 1)
			i -= 3
			x = z // 4 * 2
			y = z // 4 * 2 - 2
			j = i % 4
			if j % 4 == 0:
				return simplex(x, i // 4 * 2 + 2)
			elif j % 4 == 1 or j % 4 == 2:
				return simplex(x, i // 4 * 2 + 3)
			else:
				z1 = 0 if y < 0 else simplex(y, i // 4 * 2 + 4)
				ans = simplex(x, i // 4 * 2 + 2) - z1
				if ans < 0:
					ans += MOD
				return ans

	def F2(n):
		if n == 1:
			return [1]
		return [F1(i, n - i) for i in range(1, n + 1)]
	n = int(stdin.readline())
	a = [int(x) for x in stdin.readline().split()]
	coeffs = F2(n)
	ans = 0
	for (c, x) in zip(coeffs, a):
		ans += c * x % MOD
		if ans >= MOD:
			ans -= MOD
	stdout.write('{}\n'.format(ans))
main()


n = int(input())
p = list(map(int, input().split()))
MOD = 10 ** 9 + 7
mode = 0
if n % 4 == 3:
	n -= 1
	new = []
	for i in range(n):
		if mode == 0:
			new.append(p[i] + p[i + 1])
		else:
			new.append(p[i] - p[i + 1])
		mode = 1 - mode
	p = new

def calc0(p):
	res = 0
	ncr = 1
	n = len(p) // 2 - 1
	for i in range(n + 1):
		res = (res + ncr * (p[i * 2] - p[i * 2 + 1])) % MOD
		ncr = ncr * (n - i) * pow(i + 1, MOD - 2, MOD) % MOD
	return res

def calc1(p):
	res = 0
	ncr = 1
	n = len(p) // 2
	for i in range(n + 1):
		res = (res + ncr * p[i * 2]) % MOD
		ncr = ncr * (n - i) * pow(i + 1, MOD - 2, MOD) % MOD
	return res

def calc2(p):
	res = 0
	ncr = 1
	n = len(p) // 2 - 1
	for i in range(n + 1):
		res = (res + ncr * (p[i * 2] + p[i * 2 + 1])) % MOD
		ncr = ncr * (n - i) * pow(i + 1, MOD - 2, MOD) % MOD
	return res
print([calc0, calc1, calc2, -1][n % 4](p))


from sys import exit, stdin, stdout
n = int(stdin.readline())
a = [int(i) for i in stdin.readline().split()]
if n == 1:
	print(a[0])
	exit(0)
mod = 1000000007
f = [0] * (n + 1)
f[0] = 1
for i in range(1, n + 1):
	f[i] = f[i - 1] * i % mod

def f_pow(a, k):
	if k == 0:
		return 1
	if k % 2 == 1:
		return f_pow(a, k - 1) * a % mod
	else:
		return f_pow(a * a % mod, k // 2) % mod

def c(n, k):
	d = f[k] * f[n - k] % mod
	return f[n] * f_pow(d, mod - 2) % mod
oper = 1
while not (oper and n % 2 == 0):
	for i in range(n - 1):
		a[i] = a[i] + oper * a[i + 1]
		oper *= -1
	n -= 1
oper *= 1 if n // 2 % 2 != 0 else -1
sm1 = 0
sm2 = 0
for i in range(n):
	if i % 2 == 0:
		sm1 = (sm1 + c(n // 2 - 1, i // 2) * a[i]) % mod
	else:
		sm2 = (sm2 + c(n // 2 - 1, i // 2) * a[i]) % mod
stdout.write(str((sm1 + oper * sm2) % mod))