James is very naive in Mathematics, He always makes new things out of a given list of integers. Today he is given a list $\boldsymbol{\mbox{L}}$, so he creates a value $\mbox{S}$ out of it.  

$\mbox{S}$ from a given list can be calculated as follows.

value_of_S(list L)
{
    while ((number of elements in L) > 1)
    {
        a = L[0]
        b = L[1]
        delete L[1]
        L[0] = a+b+ab
    }
    return L[0] % 1000000007
}

James has an ample amount of time, so he calculates the values of $\mbox{S}$ for all the permutations of the given list $\boldsymbol{\mbox{L}}$ and finds their average value. Then he asks you to report that value.

Input Format 

The first line contains an integer $N$, the number of integers in the list. 

The second line contains $N$ integral values, $L[0],\ldots,L[N-1]$, separated by single spaces.

Output Format 

Print the floor of the average value.

Constraints 

$2\leq N\leq10^4$ 

$2\leq L[i]\leq10^6$

Sample Input  

2
2 3

Sample Output  

11

Explanation 

The $\mbox{S}$ value corresponding to the two permutations of the given list is $\mbox{11}$.

Difficulty: MEDIUM
Tags: Matrices

Starter code:

Solutions:
n = int(input())
a = map(int, input().split())
P = 10 ** 9 + 7
ret = 1
for x in a:
	ret = ret * (x + 1) % P
print((ret - 1) % P)


N = int(input())
L = map(int, input().split())
ans = 0
for l in L:
	ans = (l + ans + ans * l) % 1000000007
print(ans)


nums = int(input())
ints = list(map(int, input().split(' ')))
secints = [x + 1 for x in ints]
prod = 1
for i in secints:
	prod *= i
	prod %= 10 ** 9 + 7
print((prod - 1) % (10 ** 9 + 7))


n = int(input())
l = list(map(int, input().split(' ')))
result = 0
for v in l:
	result = (result + v + result * v) % 1000000007
print(result)


def value_of_S(L):
	while len(L) > 1:
		a = L[0]
		b = L[1]
		L.remove(b)
		L[0] = a + b + a * b
	return L[0] % 1000000007
num = input()
L = [int(x) for x in input().split(' ')]
import math
print(math.floor(value_of_S(L)))


N = int(input())
L = map(int, input().split()[:N])
f = 1000000007
pd = 1
for n in L:
	pd = pd * (n + 1) % f
print(pd - 1)


n = int(input())
line = input().split()
a = int(line[0])
for i in range(1, n):
	b = int(line[i])
	a = a + b + a * b
print(a % 1000000007)


n = int(input())
a = [int(x) for x in input().split()]
while len(a) > 1:
	a1 = a[0]
	a2 = a[1]
	del a[1]
	a[0] = a1 + a2 + a1 * a2
print(a[0] % 1000000007)


N = int(input())
A = str(input()).split()
res = 1
for i in range(N):
	res = res * (int(A[i]) + 1) % 1000000007
if res > 0:
	print(res - 1)
else:
	print(1000000006)


vals = int(input())
results = list(map(int, input().split()))
c = results[0]
for i in range(1, len(results)):
	c = c + results[i] + c * results[i]
print(c % 1000000007)


def func(l):
	c = len(l)
	while c > 1:
		c = c - 1
		a = l[0]
		b = l[1]
		l[0] = a + b + a * b
		l.remove(b)
	return l
a = int(input())
b = input().split(' ')
for i in range(len(b)):
	b[i] = int(b[i])
s = func(b)
print(int(s[0]) % 1000000007)


import functools

def tell_average(nlist):
	return functools.reduce(lambda x, y: x + y + x * y, nlist) % 1000000007
n = int(input())
ns = list(map(int, input().strip().split()))
print(tell_average(ns))


input()
numbers = list(map(int, input().split(' ')))
s = numbers[0]
for x in numbers[1:]:
	s = (s + x + s * x) % 1000000007
print(s)


modulo = 1000000007

def solve(A):
	sum = 0
	for i in range(1, len(A)):
		A[0] = (A[0] + A[i] + A[0] * A[i] % modulo) % modulo
	return A[0]
input()
print(solve([int(x) for x in input().split(' ')]))


n = int(input())
l = [int(j) for j in input().split()]
ans = 1
for i in l:
	ans = ans * (i + 1)
print((ans - 1) % 1000000007)


constmod = 10 ** 9 + 7
n = int(input())
a = [int(j) for j in input().strip().split()]
sum = a[0]
for x in range(1, n):
	sum += a[x] + a[x] * sum
	sum %= constmod
print(sum)


def s(t):
	val = t[0]
	for b in t[1:]:
		val = val + b + val * b
	return val % 1000000007
N = int(input())
print(s([int(x) for x in input().split()]))


n = int(input())
l = list(map(int, input().strip().split()))
p = int(1000000000.0) + 7
ans = l[0]
for i in range(n - 1):
	val = l[i + 1]
	ans = ((1 + ans) * (1 + val) - 1) % p
ans %= p
print(ans)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


import sys
MOD = 1000000007
N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))
for i in range(1, N):
	L[0] = (L[0] + L[i] + L[0] * L[i]) % MOD
print(L[0])


MOD = 1000000007
N = int(input())
L = [int(_) for _ in input().split()]
s = 1
for l in L:
	s *= l + 1
	s %= MOD
print((s + MOD - 1) % MOD)


n = int(input())
l = input().split()
l = list(map(int, l))
for i in range(n - 1):
	a = l[0]
	b = l[1]
	l.remove(l[1])
	l[0] = (a + b + a * b) % 1000000007
print(l[0])


a = int(input())
b = input().split(' ')
b = [int(i) for i in b]
for i in range(1, a):
	b[0] = b[i] * b[0] + b[0] + b[i]
	b[0] %= 1000000007
print(b[0])


i = 1
j = int(input())
numbers = map(int, input().split())
for _ in numbers:
	i = i * (_ + 1) % 1000000007
i -= 1
print(i)


n = int(input())
arr = [int(x) for x in input().split()]
res = 1
for x in arr:
	res = res * (x + 1) % 1000000007
print(res - 1)


def value_of_S(L):
	while len(L) > 1:
		a = L[0]
		b = L[1]
		del L[1]
		L[0] = a + b + a * b
	return L[0] % 1000000007
n = int(input())
l = [int(i) for i in input().split()]
print(value_of_S(l))


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


N = int(input())
L = [int(ns) for ns in str(input()).split()]
for i in range(1, N):
	a = L[0]
	b = L[i]
	L[0] = (a + b + a * b) % 1000000007
print(L[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


import sys
number_count = int(sys.stdin.readline().strip())
numbers = sys.stdin.readline().strip().split()
s_step1 = None
for number in numbers:
	if not s_step1:
		s_step1 = int(number)
		continue
	s_step1 = s_step1 + int(number) + s_step1 * int(number)
print(s_step1 % 1000000007)


import sys
MOD = 1000000007
N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))
for i in range(1, N):
	L[0] = (L[0] + L[i] + L[0] * L[i]) % MOD
print(L[0])


import sys
MOD = 1000000007
N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))
for i in range(1, N):
	L[0] = (L[0] + L[i] + L[0] * L[i]) % MOD
print(L[0])


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


n = int(input())
L = [int(i) for i in input().split()]
while len(L) > 1:
	a = L[0]
	b = L[1]
	del L[1]
	L[0] = (a + b + a * b) % 1000000007
print(L[0])


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


N = int(input())
K = map(int, input().split())
L = []
for (b, d) in enumerate(K):
	L.append(int(d))
while len(L) > 1:
	a = L[0]
	b = L[1]
	L.remove(L[1])
	L[0] = a % (10 ** 9 + 7) + b % (10 ** 9 + 7) + a % (10 ** 9 + 7) * b % (10 ** 9 + 7) % (10 ** 9 + 7)
print(L[0] % (10 ** 9 + 7))


import math

def value_of_S(L):
	while len(L) > 1:
		a = L[0]
		b = L[1]
		del L[1]
		L[0] = a + b + a * b
	return L[0] % 1000000007
input()
print(math.floor(value_of_S(list(map(int, input().split(' '))))))


__author__ = 'vikas'
n = int(input())
s = input()
s = s.split(' ')
l = list(map(int, s))
result = 1
m = 1000000007

def mod(a, b):
	return (a % b + b) % b
for i in l:
	result = mod(result * (1 + i), m)
print(mod(result - 1, m))


from itertools import permutations
from functools import reduce
n = input()
array = map(int, input().split())
print(reduce(lambda a, b: a + b + a * b, array) % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(n, l) = (int(input()), [int(x) for x in input().split()])
while len(l) > 1:
	l[0] += l[1] + l[0] * l[1]
	l.pop(1)
print(l[0] % 1000000007)


N = int(input())
modulo = 1000000007
arr = [int(x) for x in input().split()]
prod = 1
for item in arr:
	prod = prod * (item + 1) % modulo
if prod == 0:
	prod = modulo - 1
else:
	prod -= 1
print(prod)


import functools
N = int(input())
L = input().split()
L = list(map(int, L))

def f(x, y):
	return x + y + x * y
S = functools.reduce(f, L) % 1000000007
print(S)


n = int(input())
l = [int(x) for x in input().split()]
m = 0
s = l[0]
for x in range(1, len(l)):
	s = s + l[x] + s * l[x]
	m += s
print(s % 1000000007)


import sys
MOD = 1000000007
N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))
for i in range(1, N):
	L[0] = (L[0] + L[i] + L[0] * L[i]) % MOD
print(L[0])


n = int(input())
a = [int(x) for x in input().split()]
for i in range(1, n):
	a[0] += a[i] + a[0] * a[i]
print(a[0] % 1000000007)


n = int(input())
b = input().split()
a = []
for v in b:
	a.append(int(v))
k = n - 1
mod = 1000000007
while k > 0:
	a[0] = (a[0] + a[k] + a[0] * a[k]) % mod
	k = k - 1
print(a[0])


def value_of_S(lst):
	while len(lst) > 1:
		(a, b) = (lst[0], lst[1])
		del lst[1]
		lst[0] = a + b + a * b
	return lst[0] % 1000000007
N = int(input())
print(value_of_S(list(map(int, input().split()))))


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


from math import factorial, floor

def s(l):
	while len(l) > 1:
		a = l[0]
		b = l[1]
		l.pop(1)
		l[0] = a + b + a * b
	return l[0] % 1000000007
n = int(input())
print(floor(s(list(map(int, input().split())))))


import math

def value_of_S(L):
	length = len(L)
	while length > 1:
		a = L[0]
		b = L[1]
		L.pop(1)
		L[0] = a + b + a * b
		length = len(L)
	return L[0] % 1000000007
n = int(input())
li = list(map(int, input().split()))
print(math.floor(value_of_S(li)))


from functools import reduce
modo = 1000000007

def do(l):
	return reduce(lambda x, y: (x * (1 + y) + y) % modo, l)
N = int(input().strip())
L = list((int(i) for i in input().strip().split()))
print(do(L))


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(N, L) = (int(input()), list(map(int, input().strip().split())))
for i in range(len(L) - 1):
	L[0] = L[0] + L[1] + L[0] * L[1]
	del L[1]
print(L[0] % 1000000007)


from functools import reduce

def value_S(L, s=1000000000.0 + 7):
	return int(reduce(lambda x, y: x * y % s, [1 + a for a in L]) - 1)
N = int(input())
L = [int(c) for c in input().split(' ')]
print(value_S(L))


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


m = pow(10, 9) + 7
a = []
out = 0
n = int(input())
s = input()
t = s.split()
a = list(map(int, t))
s = 1
for j in range(0, n):
	s = s * (a[j] + 1) % m % m
out = (s - 1) % m
print(out)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


import sys

def solve(a, m):
	u = 1
	for v in a:
		u *= v + 1
		u %= m
	return (u - 1) % m
_ = int(input())
a = list(map(int, input().split()))
m = pow(10, 9) + 7
print(solve(a, m))


def val(l):
	while len(l) > 1:
		a = l[0]
		b = l[1]
		del l[1]
		l[0] = a + b + a * b
	return l[0] % (10 ** 9 + 7)
n = int(input())
l = list(map(int, input().split()))
print(val(l))


N = int(input().strip())
L = [int(x) for x in input().strip().split(' ')][::-1]
avg = L[-1]
del L[-1]
for i in range(N - 1):
	avg = avg + L[-1] + avg * L[-1]
	del L[-1]
print(avg % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


from functools import reduce
print((lambda _, u: reduce(lambda x, y: (x + y + x * y) % 1000000007, u))(input(), map(int, input().split())))


from functools import reduce
N = int(input())
L = list(map(int, input().split()))
print(reduce(lambda x, y: (x + y + x * y) % 1000000007, L))


N = int(input())

def S(myL):
	while len(myL) > 1:
		a = myL[0]
		b = myL[1]
		del myL[1]
		myL[0] = a + b + a * b
	return myL[0] % 1000000007
mylist = [int(i) for i in input().split()]
print(S(mylist))


n = int(input())
a = input().split()
for i in range(n):
	a[i] = int(a[i])
for i in range(n - 2, -1, -1):
	a[i] = a[i] + a[i + 1] + a[i] * a[i + 1]
print(a[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


n = int(input())
l = [int(i) for i in input().split()]
while len(l) > 1:
	a = l[0]
	b = l[1]
	l.pop(1)
	l[0] = a + b + a * b
print(l[0] % 1000000007)


from functools import reduce

def op(a, b, p=10 ** 9 + 7):
	return (a + b + a * b) % p

def main():
	input()
	print(reduce(op, map(int, input().split())))
main()


import sys
n = int(input())
l = [int(x) for x in input().split(' ')]
while len(l) > 1:
	a = l.pop(0)
	l[0] = l[0] + a + l[0] * a
print(l[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


n = int(input())
l = list(map(int, input().split()))
while len(l) > 1:
	(a, b) = (l[0], l[1])
	l[0] = a + b + a * b
	l.remove(l[1])
print(l[0] % 1000000007)


N = int(input().strip())
L = [int(arr_temp) for arr_temp in input().strip().split(' ')]
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


P = 1000000007
N = int(input())
x = input().split()
L = {i: int(x[i]) for i in range(N)}
i = 1
while len(L) > 1:
	a = L[0]
	b = L[i]
	L[0] = (a + b + a * b) % P
	L.pop(i)
	i += 1
print(L[0])


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


t = int(input())
l = map(int, input().split())
r = 1
for e in l:
	r *= e + 1
r -= 1
print(r % 1000000007)


n = int(input())
l = list(map(int, input().split()))
prod = 1
for i in l:
	prod *= i + 1
print((prod - 1) % (pow(10, 9) + 7))


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


from math import *
n = int(input())
a = list(map(int, input().split()))

def find(a):
	while len(a) > 1:
		x = a[0]
		y = a[1]
		del a[1]
		a[0] = x + y + x * y
	return a[0] % (10 ** 9 + 7)
ans = find(a)
print(ans)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(n, l) = (int(input()), list(map(int, input().split())))
while len(l) > 1:
	l[0] += l[1] + l[0] * l[1]
	del l[1]
print(l[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


from functools import reduce
N = int(1000000000.0) + 7

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

def mult(a, b):
	return a * b % N

def f(a, b):
	return add(add(a, b), mult(a, b))
n = input()
print(reduce(f, map(int, input().split())))


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


import math
input()
L = [int(i) for i in input().split()]
for i in range(1, len(L)):
	L[0] = L[0] + L[i] + L[0] * L[i]
print(L[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


(N, L) = (int(input()), [int(n) for n in input().split()])
while len(L) > 1:
	L[0] += L[1] + L[0] * L[1]
	L.pop(1)
print(L[0] % 1000000007)


N = int(input().strip())
nums = [int(i) for i in input().strip().split(' ')]
total = 0
if len(nums) > 0:
	total = nums[0]
for i in nums[1:]:
	total = (total + i * total + i) % 1000000007
print(total)


N = int(input())
m = 1000000007
L = [int(l) for l in input().split()]
prod = 1
for l in L:
	prod = prod * (l + 1) % m
print(prod - 1)


n = int(input())
p = 1
for i in map(int, input().split(' ')):
	p = p * (i + 1) % 1000000007
print((p - 1) % 1000000007)


n = int(input())
l = [int(i) for i in input().split()]
a = l[0]
b = l[1]
for h in range(1, len(l)):
	b = l[h]
	a = (a + b + a * b) % 1000000007
print(a)


N = int(input())
L = list(map(int, input().split()))
L0 = L[0]
for itest in range(1, N):
	L1 = L[itest]
	L0 = (L0 + L1 + L0 * L1) % 1000000007
print(L0)


def value(li):
	while len(li) > 1:
		a = li[0]
		b = li[1]
		li.pop(1)
		li[0] = a + b + a * b
	return li[0] % 1000000007
t = int(input())
li = list(map(int, input().split()))
print(value(li))