With the college fest approaching soon, Manasa is following a strict dieting regime . Today, she just cannot resist her temptation for having a pizza. An inner conflict ensues, and she decides that she will have a pizza, only if she comes up with a solution to the problem stated below. Help her get the pizza for herself.

Given a list L of N numbers, where 

L = { a_{1}, a_{2}, a_{3}, a_{4} ....  , a_{N}} 

Find the value of M that is computed as described below.  

Input Format 

The first line contains an integer N i.e. size of the list L. 

The next line contains N space separated integers, each representing an element of the list L.  

Output Format 

Print the value of M _modulo (10^{9} + 7)_. 

Constraints 

1 ≤ N ≤ 5100

0 ≤ a_{i} ≤ 10^{15} , where i ∈ [1 .. N]

Sample Input 00  

3
1 2 3

Sample Output 00  

40392

Explanation

There are 8 subsets of given set,

S = {1,2,3} and L - S  ={0} value of F(6) = 19601
S = {1,2} and L - S  ={3} value of F(0) = 1
S = {1,3} and L - S  ={2} value of F(2) = 17
S = {2,3} and L - S  ={1} value of F(4) = 577
S = {1} and L - S  ={2,3} value of F(4) = 577
S = {2} and L - S  ={1,3} value of F(2) = 17
S = {3} and L - S  ={1,2} value of F(0) = 1
S = {} and L - S  ={1,2,3} value of F(6) = 19601

Adding all these values, we get M = 40392.

Source: hackerrank | Difficulty: MEDIUM
Tags: Matrices


Solutions:
from random import randint
from collections import Counter
from functools import reduce
from itertools import accumulate, combinations, takewhile, product
home = 0
lire = 1
trace = 0
mp = 10 ** 6
if home:
	from mesures import ch
modo = 10 ** 9 + 7
pars = []

class Lucmat:

	def __init__(s, P, Q, Iv, modo):
		(s.matBase, s.modo, s.pows, po, s.Iv) = ([[P, -Q], [1, 0]], modo, {}, 1, Iv)
		s.pows[1] = s.matBase
		s.mbl = 1
		s.modo = modo

	def sqmatmulmod(s, m1, m2):
		mr = list(([0] * 2 for _ in range(2)))
		for l in range(len(m1)):
			for c in range(len(m1)):
				mr[l][c] = sum((m1[l][ix] * m2[ix][c] for ix in range(len(m1)))) % s.modo
		return mr

	def do(s, po):
		if po < 2:
			return s.Iv[po]
		if trace & 1:
			print('expMat', po)
		for bl in range(s.mbl, po.bit_length()):
			s.pows[bl + 1] = s.sqmatmulmod(s.pows[bl], s.pows[bl])
		if trace & 2:
			print('\t', s.pows)
		s.mbl = po.bit_length()
		pc = 1
		while not po & 1:
			(po, pc) = (po >> 1, pc + 1)
		(rm, pc, po) = (s.pows[pc], pc + 1, po >> 1)
		while po:
			if trace & 2:
				print(po, pc)
			if po & 1:
				rm = s.sqmatmulmod(s.pows[pc], rm)
			(pc, po) = (pc + 1, po >> 1)
		return rm[0][0] * s.Iv[0] + rm[0][1] * s.Iv[1]

def faire(s):
	Fm = Lucmat(6, 1, (1, 3), modo)
	r = 1
	for v in s:
		r = 2 * r * Fm.do(v) % modo
	return r
if home and (not lire):
	cr = ch()
	for Nbs in ((1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5), (100, 103, 207, 209), (100, 103, 207, 209, 709), (100, 103, 207, 209, 709, 713), (100, 103, 207, 209, 709, 713, 1003), (100, 103, 207, 209, 709, 713, 1003, 2041)):
		print(Nbs)
		for f in (stupid, stupidm1, stupid4, stupid5):
			cr.rst()
			r = f(Nbs)
			t = cr.lap()
			print('\t', f.__name__, sum(Nbs), r, t)
else:
	input()
	Nbs = list((int(i) for i in input().strip().split()))
print(faire(Nbs))


import sys
from time import time
from functools import lru_cache

def mat_mul(A, B, m):
	return ((A[0] * B[0] + A[1] * B[2]) % m, (A[0] * B[1] + A[1] * B[3]) % m, (A[2] * B[0] + A[3] * B[2]) % m, (A[2] * B[1] + A[3] * B[3]) % m)

def mat_mul_scalar(A, f, m):
	return (A[0] * f % m, A[1] * f % m, A[2] * f % m, A[3] * f % m)

def mat_add(A, B, m):
	return ((A[0] + B[0]) % m, (A[1] + B[1]) % m, (A[2] + B[2]) % m, (A[3] + B[3]) % m)

@lru_cache()
def mat_pow(A, p, m):
	C = (1, 0, 0, 1)
	if p == 0:
		return C
	while p != 0:
		if p % 2 == 1:
			C = mat_mul(C, A, m)
		A = mat_mul(A, A, m)
		p //= 2
	return C

def f(n, m):
	F = (0, -1, 1, 6)
	P = mat_pow(F, n, m)
	return (P[0] + 3 * P[2]) % m

def subset_sum_gen(aa):
	total = sum(aa)
	ii = tuple(range(len(aa)))
	stack = [(0, 0)]
	while stack:
		(index, sm) = stack.pop()
		yield abs(total - 2 * sm)
		for new_index in range(index + 1, len(aa)):
			new_sm = sm + aa[new_index]
			stack.append((new_index, new_sm))

def get_subset_sums(aa):
	total = sum(aa)
	cache = {0: 1}
	for a in aa:
		delta = dict()
		for (sm, cnt) in cache.items():
			new_sm = sm + a
			if new_sm in delta:
				delta[new_sm] += cnt
			else:
				delta[new_sm] = cnt
		for (sm, cnt) in delta.items():
			if sm in cache:
				cache[sm] += cnt
			else:
				cache[sm] = cnt
	return cache

def solve_bf(aa, m):
	cache = dict()
	sm = 0
	for n in subset_sum_gen(aa):
		if n in cache:
			cache[n] += 1
		else:
			cache[n] = 1
		u = f(n, m)
		sm += u
		sm %= m
	sm *= 2
	sm %= m
	return sm

def solve_slow(aa, m):
	print('laa=%s' % (len(aa),), file=sys.stderr)
	total = sum(aa)
	ssums = get_subset_sums(aa)
	print('lssums=%s' % (len(ssums),), file=sys.stderr)
	cache = dict()
	for (sm, cnt) in ssums.items():
		r = abs(total - 2 * sm)
		if r in cache:
			cache[r] += cnt
		else:
			cache[r] = cnt
	(sm, total) = (0, sum(aa))
	for (n, cnt) in cache.items():
		u = f(n, m)
		sm += u * cnt % m
		sm %= m
	return sm

def solve_alt(aa, m):
	ssums = get_subset_sums(aa)
	(P, F, total) = ((0, 0, 0, 0), (0, -1, 1, 6), sum(aa))
	for (n, cnt) in ssums.items():
		A = mat_pow(F, n * 2, m)
		A = mat_mul_scalar(A, cnt, m)
		P = mat_add(P, A, m)
	F_inv = (6, 1, -1, 0)
	F_inv_total = mat_pow(F_inv, total, m)
	P = mat_mul(P, F_inv_total, m)
	rval = (P[0] + 3 * P[2]) % m
	return rval

def solve(aa, m):
	(I, F, F_inv, total) = ((1, 0, 0, 1), (0, -1, 1, 6), (6, 1, -1, 0), sum(aa))
	a = aa[0]
	P = mat_pow(F, 2 * a, m)
	print('a=%d P=%s' % (a, P), file=sys.stderr)
	for a in aa[1:]:
		Q = mat_pow(F, 2 * a, m)
		Q = mat_add(I, Q, m)
		P = mat_mul(P, Q, m)
		print('a=%d P=%s Q=%s' % (a, P, Q), file=sys.stderr)
	F_inv_total = mat_pow(F_inv, total, m)
	P = mat_mul(P, F_inv_total, m)
	rval = (P[0] + 3 * P[2]) % m
	return rval * 2 % m
tm = time()
_ = int(input())
aa = tuple(map(int, input().split()))
m = pow(10, 9) + 7
print(solve(aa, m))
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


(d, u, v) = (10 ** 9 + 7, [6, -1, 1, 0], [0, 1, -1, 6])

def ml(l, r):
	((x, y, z, w), (h, i, j, k)) = (l, r)
	return ((x * h + z * i) % d, (y * h + w * i) % d, (x * j + z * k) % d, (y * j + w * k) % d)

def slv(l, r):
	if r == 0:
		return (1, 0, 0, 1)
	if r & 1:
		return ml(slv(l, r - 1), l)
	return slv(ml(l, l), r // 2)
n = int(input())
l = list(map(int, input().split()))
a = [1, 0, 0, 1]
for i in l:
	(x, y) = (slv(u, i), slv(v, i))
	a = ml(a, (x[0] + y[0], x[1] + y[1], x[2] + y[2], x[3] + y[3]))
a = ml(a, v)
print((3 * a[0] + a[1]) % d)


(d, u, v) = (10 ** 9 + 7, [6, -1, 1, 0], [0, 1, -1, 6])

def ml(l, r):
	((x, y, z, w), (h, i, j, k)) = (l, r)
	return ((x * h + z * i) % d, (y * h + w * i) % d, (x * j + z * k) % d, (y * j + w * k) % d)

def slv(l, r):
	if r == 0:
		return (1, 0, 0, 1)
	if r & 1:
		return ml(slv(l, r - 1), l)
	return slv(ml(l, l), r // 2)
n = int(input())
l = list(map(int, input().split()))
a = [1, 0, 0, 1]
for i in l:
	(x, y) = (slv(u, i), slv(v, i))
	a = ml(a, (x[0] + y[0], x[1] + y[1], x[2] + y[2], x[3] + y[3]))
a = ml(a, v)
print((3 * a[0] + a[1]) % d)


MOD = 1000000007
(base1, base2) = (880572810, 119427203)
input()
A = [int(x) for x in input().split()]
(sum1, sum2) = (1, 1)
for a in A:
	sum1 = sum1 * (1 + pow(base1, 2 * a, MOD)) % MOD
	sum2 = sum2 * (1 + pow(base2, 2 * a, MOD)) % MOD
sum_A = sum(A)
sum1 = sum1 * pow(base2, sum_A, MOD) % MOD
sum2 = sum2 * pow(base1, sum_A, MOD) % MOD
result = (sum1 + sum2) * (MOD + 1) // 2 % MOD
print(result)


P = 10 ** 9 + 7

def inv_mod(n):
	return pow(n, P - 2, P)

class Matrix2:

	def __init__(self, a=1, b=0, c=0, d=1):
		(self.m00, self.m01, self.m10, self.m11) = (a % P, b % P, c % P, d % P)

	def __add__(self, B):
		return Matrix2(self.m00 + B.m00, self.m01 + B.m01, self.m10 + B.m10, self.m11 + B.m11)

	def __mul__(self, B):
		return Matrix2(self.m00 * B.m00 + self.m01 * B.m10, self.m00 * B.m01 + self.m01 * B.m11, self.m10 * B.m00 + self.m11 * B.m10, self.m10 * B.m01 + self.m11 * B.m11)

	def __pow__(self, n):
		if n == 0:
			return Matrix2()
		if n < 0:
			return self.inverse() ** (-n)
		if n & 1 == 0:
			return (self * self) ** (n >> 1)
		return self * (self * self) ** (n >> 1)

	def det(self):
		return (self.m00 * self.m11 - self.m10 * self.m01) % P

	def inverse(self):
		det = self.det()
		assert det != 0
		inv_det = inv_mod(det)
		return Matrix2(self.m11 * inv_det, -self.m01 * inv_det, -self.m10 * inv_det, self.m00 * inv_det)

	def eval(self, u0=1, u1=3):
		return (self.m00 * u0 + self.m01 * u1) % P

def main():
	F = Matrix2(0, 1, -1, 6)
	N = int(input())
	A = list(map(int, input().split()))
	S = Matrix2()
	for a in A:
		S *= F ** a + F ** (-a)
	print(S.eval())
main()


modulo_constant = 10 ** 9 + 7

def mx_times(a, b, mo):
	return [[sum((a * b for (a, b) in zip(a_row, b_col))) % mo for b_col in zip(*b)] for a_row in a]

def mx_pow(mx, n, mo):
	rank = len(mx)
	ret = [[0] * i + [1] + (rank - i - 1) * [0] for i in range(rank)]
	while n:
		if n & 1:
			ret = mx_times(ret, mx, mo)
		n >>= 1
		mx = mx_times(mx, mx, mo)
	return ret
from functools import lru_cache

@lru_cache(maxsize=None)
def ff(n):
	mx = mx_pow([[0, 1], [-1, 6]], n, modulo_constant)
	return (mx[1][1] - 3 * mx[0][1]) % modulo_constant

def subset_sum(vec):
	ret = 1
	for x in vec:
		ret *= 2 * ff(x)
		ret %= modulo_constant
	return ret

def run_subset_sum(reader=input, printer=print):
	n = int(reader())
	vec = [int(x) for x in reader().split()]
	assert n == len(vec)
	printer(str(subset_sum(vec)))
run_subset_sum()


mod = 1000000007

def matpow(a, n, x):
	toret = []
	for i in range(n):
		row = [0] * n
		row[i] = 1
		toret.append(row)
	apow2 = a
	curr = x
	while curr > 0:
		if curr % 2 == 1:
			nextret = []
			for i in range(n):
				row = [0] * n
				for j in range(n):
					for k in range(n):
						row[j] = (row[j] + toret[i][k] * apow2[k][j]) % mod
				nextret.append(row)
			toret = nextret
		nextapow = []
		for i in range(n):
			row = [0] * n
			for j in range(n):
				for k in range(n):
					row[j] = (row[j] + apow2[i][k] * apow2[k][j]) % mod
			nextapow.append(row)
		apow2 = nextapow
		curr //= 2
	return toret
n = int(input())
a = list(map(int, input().split(' ')))
currmat = [[1, 0], [0, 1]]
basemat = [[0, 1], [-1, 6]]
baseinv = [[6, -1], [1, 0]]
for x in a:
	multmat1 = matpow(basemat, 2, x)
	multmat2 = matpow(baseinv, 2, x)
	diffmat = [[0, 0], [0, 0]]
	for i in range(2):
		for j in range(2):
			diffmat[i][j] = multmat1[i][j] + multmat2[i][j]
	nextmat = [[0, 0], [0, 0]]
	for i in range(2):
		for j in range(2):
			for k in range(2):
				nextmat[i][j] = (nextmat[i][j] + currmat[i][k] * diffmat[k][j]) % mod
	currmat = nextmat
print(currmat[0][0])


N = int(input())
mod = 1000000007
now = 1
for i in input().split():
	now *= pow(119427203, int(i), mod) + pow(880572810, int(i), mod)
	if now >= mod:
		now %= mod
print(now)


from operator import mul
MOD = 10 ** 9 + 7
ONE2 = [[1, 0], [0, 1]]

def mmul(m1, m2):
	m2 = list(zip(*m2))
	return [[sum(map(mul, row, col)) % MOD for col in m2] for row in m1]

def m2add(m1, m2):
	((a11, a12), (a21, a22)) = m1
	((b11, b12), (b21, b22)) = m2
	return [[(a11 + b11) % MOD, (a12 + b12) % MOD], [(a21 + b21) % MOD, (a22 + b22) % MOD]]

def m2pow(m, e):
	if e < 0:
		raise ValueError('forget it')
	ret = [[1, 0], [0, 1]]
	while e > 0:
		if e & 1:
			ret = mmul(ret, m)
		m = mmul(m, m)
		e //= 2
	return ret

def solve(L):
	x = [[6, -1], [1, 0]]
	xinv = [[0, 1], [-1, 6]]
	a = sum(L)
	r = m2pow(xinv, a)
	for ai in L:
		r = mmul(r, m2add(ONE2, m2pow(x, 2 * ai)))
	r = mmul(r, [[3], [1]])
	return r[1][0]
input()
L = list(map(int, input().split()))
print(solve(L))


from random import randint
from collections import Counter
from functools import reduce
from itertools import accumulate, combinations, takewhile, product
home = 0
lire = 1
trace = 0
mp = 10 ** 6
if home:
	from mesures import ch
modo = 10 ** 9 + 7
pars = []

class Lucmat:

	def __init__(s, P, Q, Iv, modo):
		(s.matBase, s.modo, s.pows, po, s.Iv) = ([[P, -Q], [1, 0]], modo, {}, 1, Iv)
		s.pows[1] = s.matBase
		s.mbl = 1
		s.modo = modo

	def sqmatmulmod(s, m1, m2):
		mr = list(([0] * 2 for _ in range(2)))
		for l in range(len(m1)):
			for c in range(len(m1)):
				mr[l][c] = sum((m1[l][ix] * m2[ix][c] for ix in range(len(m1)))) % s.modo
		return mr

	def do(s, po):
		if po < 2:
			return s.Iv[po]
		if trace & 1:
			print('expMat', po)
		for bl in range(s.mbl, po.bit_length()):
			s.pows[bl + 1] = s.sqmatmulmod(s.pows[bl], s.pows[bl])
		if trace & 2:
			print('\t', s.pows)
		s.mbl = po.bit_length()
		pc = 1
		while not po & 1:
			(po, pc) = (po >> 1, pc + 1)
		(rm, pc, po) = (s.pows[pc], pc + 1, po >> 1)
		while po:
			if trace & 2:
				print(po, pc)
			if po & 1:
				rm = s.sqmatmulmod(s.pows[pc], rm)
			(pc, po) = (pc + 1, po >> 1)
		return rm[0][0] * s.Iv[0] + rm[0][1] * s.Iv[1]

def faire(s):
	Fm = Lucmat(6, 1, (1, 3), modo)
	r = 1
	for v in s:
		r = 2 * r * Fm.do(v) % modo
	return r
if home and (not lire):
	cr = ch()
	for Nbs in ((1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5), (100, 103, 207, 209), (100, 103, 207, 209, 709), (100, 103, 207, 209, 709, 713), (100, 103, 207, 209, 709, 713, 1003), (100, 103, 207, 209, 709, 713, 1003, 2041)):
		print(Nbs)
		for f in (stupid, stupidm1, stupid4, stupid5):
			cr.rst()
			r = f(Nbs)
			t = cr.lap()
			print('\t', f.__name__, sum(Nbs), r, t)
else:
	input()
	Nbs = list((int(i) for i in input().strip().split()))
print(faire(Nbs))


from random import randint
from collections import Counter
from functools import reduce
from itertools import accumulate, combinations, takewhile, product
home = 0
lire = 1
trace = 0
mp = 10 ** 6
if home:
	from mesures import ch
modo = 10 ** 9 + 7
pars = []

class Lucmat:

	def __init__(s, P, Q, Iv, modo):
		(s.matBase, s.modo, s.pows, po, s.Iv) = ([[P, -Q], [1, 0]], modo, {}, 1, Iv)
		s.pows[1] = s.matBase
		s.mbl = 1
		s.modo = modo

	def sqmatmulmod(s, m1, m2):
		mr = list(([0] * 2 for _ in range(2)))
		for l in range(len(m1)):
			for c in range(len(m1)):
				mr[l][c] = sum((m1[l][ix] * m2[ix][c] for ix in range(len(m1)))) % s.modo
		return mr

	def do(s, po):
		if po < 2:
			return s.Iv[po]
		if trace & 1:
			print('expMat', po)
		for bl in range(s.mbl, po.bit_length()):
			s.pows[bl + 1] = s.sqmatmulmod(s.pows[bl], s.pows[bl])
		if trace & 2:
			print('\t', s.pows)
		s.mbl = po.bit_length()
		pc = 1
		while not po & 1:
			(po, pc) = (po >> 1, pc + 1)
		(rm, pc, po) = (s.pows[pc], pc + 1, po >> 1)
		while po:
			if trace & 2:
				print(po, pc)
			if po & 1:
				rm = s.sqmatmulmod(s.pows[pc], rm)
			(pc, po) = (pc + 1, po >> 1)
		return rm[0][0] * s.Iv[0] + rm[0][1] * s.Iv[1]

def faire(s):
	Fm = Lucmat(6, 1, (1, 3), modo)
	r = 1
	for v in s:
		r = 2 * r * Fm.do(v) % modo
	return r
if home and (not lire):
	cr = ch()
	for Nbs in ((1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5), (100, 103, 207, 209), (100, 103, 207, 209, 709), (100, 103, 207, 209, 709, 713), (100, 103, 207, 209, 709, 713, 1003), (100, 103, 207, 209, 709, 713, 1003, 2041)):
		print(Nbs)
		for f in (stupid, stupidm1, stupid4, stupid5):
			cr.rst()
			r = f(Nbs)
			t = cr.lap()
			print('\t', f.__name__, sum(Nbs), r, t)
else:
	input()
	Nbs = list((int(i) for i in input().strip().split()))
print(faire(Nbs))


from random import randint
from collections import Counter
from functools import reduce
from itertools import accumulate, combinations, takewhile, product
home = 0
lire = 1
trace = 0
mp = 10 ** 6
if home:
	from mesures import ch
modo = 10 ** 9 + 7
pars = []

class Lucmat:

	def __init__(s, P, Q, Iv, modo):
		(s.matBase, s.modo, s.pows, po, s.Iv) = ([[P, -Q], [1, 0]], modo, {}, 1, Iv)
		s.pows[1] = s.matBase
		s.mbl = 1
		s.modo = modo

	def sqmatmulmod(s, m1, m2):
		mr = list(([0] * 2 for _ in range(2)))
		for l in range(len(m1)):
			for c in range(len(m1)):
				mr[l][c] = sum((m1[l][ix] * m2[ix][c] for ix in range(len(m1)))) % s.modo
		return mr

	def do(s, po):
		if po < 2:
			return s.Iv[po]
		if trace & 1:
			print('expMat', po)
		for bl in range(s.mbl, po.bit_length()):
			s.pows[bl + 1] = s.sqmatmulmod(s.pows[bl], s.pows[bl])
		if trace & 2:
			print('\t', s.pows)
		s.mbl = po.bit_length()
		pc = 1
		while not po & 1:
			(po, pc) = (po >> 1, pc + 1)
		(rm, pc, po) = (s.pows[pc], pc + 1, po >> 1)
		while po:
			if trace & 2:
				print(po, pc)
			if po & 1:
				rm = s.sqmatmulmod(s.pows[pc], rm)
			(pc, po) = (pc + 1, po >> 1)
		return rm[0][0] * s.Iv[0] + rm[0][1] * s.Iv[1]

def faire(s):
	Fm = Lucmat(6, 1, (1, 3), modo)
	r = 1
	for v in s:
		r = 2 * r * Fm.do(v) % modo
	return r
if home and (not lire):
	cr = ch()
	for Nbs in ((1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5), (100, 103, 207, 209), (100, 103, 207, 209, 709), (100, 103, 207, 209, 709, 713), (100, 103, 207, 209, 709, 713, 1003), (100, 103, 207, 209, 709, 713, 1003, 2041)):
		print(Nbs)
		for f in (stupid, stupidm1, stupid4, stupid5):
			cr.rst()
			r = f(Nbs)
			t = cr.lap()
			print('\t', f.__name__, sum(Nbs), r, t)
else:
	input()
	Nbs = list((int(i) for i in input().strip().split()))
print(faire(Nbs))


from random import randint
from collections import Counter
from functools import reduce
from itertools import accumulate, combinations, takewhile, product
home = 0
lire = 1
trace = 0
mp = 10 ** 6
if home:
	from mesures import ch
modo = 10 ** 9 + 7
pars = []

class Lucmat:

	def __init__(s, P, Q, Iv, modo):
		(s.matBase, s.modo, s.pows, po, s.Iv) = ([[P, -Q], [1, 0]], modo, {}, 1, Iv)
		s.pows[1] = s.matBase
		s.mbl = 1
		s.modo = modo

	def sqmatmulmod(s, m1, m2):
		mr = list(([0] * 2 for _ in range(2)))
		for l in range(len(m1)):
			for c in range(len(m1)):
				mr[l][c] = sum((m1[l][ix] * m2[ix][c] for ix in range(len(m1)))) % s.modo
		return mr

	def do(s, po):
		if po < 2:
			return s.Iv[po]
		if trace & 1:
			print('expMat', po)
		for bl in range(s.mbl, po.bit_length()):
			s.pows[bl + 1] = s.sqmatmulmod(s.pows[bl], s.pows[bl])
		if trace & 2:
			print('\t', s.pows)
		s.mbl = po.bit_length()
		pc = 1
		while not po & 1:
			(po, pc) = (po >> 1, pc + 1)
		(rm, pc, po) = (s.pows[pc], pc + 1, po >> 1)
		while po:
			if trace & 2:
				print(po, pc)
			if po & 1:
				rm = s.sqmatmulmod(s.pows[pc], rm)
			(pc, po) = (pc + 1, po >> 1)
		return rm[0][0] * s.Iv[0] + rm[0][1] * s.Iv[1]

def faire(s):
	Fm = Lucmat(6, 1, (1, 3), modo)
	r = 1
	for v in s:
		r = 2 * r * Fm.do(v) % modo
	return r
if home and (not lire):
	cr = ch()
	for Nbs in ((1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5), (100, 103, 207, 209), (100, 103, 207, 209, 709), (100, 103, 207, 209, 709, 713), (100, 103, 207, 209, 709, 713, 1003), (100, 103, 207, 209, 709, 713, 1003, 2041)):
		print(Nbs)
		for f in (stupid, stupidm1, stupid4, stupid5):
			cr.rst()
			r = f(Nbs)
			t = cr.lap()
			print('\t', f.__name__, sum(Nbs), r, t)
else:
	input()
	Nbs = list((int(i) for i in input().strip().split()))
print(faire(Nbs))