# TLE
N = int(input())
A = list(map(int, input().split()))

md = 1000000007

ret, prod = 0, 1
d23 = 2 * pow(3, md - 2, md)

for i, a in enumerate(A):
    ret *= 3  # mod をとっていない
    if prod:
        prod = prod * a % md
        ret += prod * (d23 if i < N - 1 else 1) % md
    else:
        ret *= pow(3, N - 1 - i, md)
        break

print(ret % md)