MOD = 10**9 + 7

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

if N == 0:
    print(0)
elif N == 1:
    print(A[0] % MOD)
else:
    sum_total = 0
    prod_total = A[0] % MOD
    count = 1

    for i in range(1, N):
        a = A[i] % MOD
        # Contributions from '+', '-', '*'
        new_sum_plus = (sum_total + prod_total) % MOD
        new_prod_plus = (a * count) % MOD
        
        new_sum_minus = (sum_total + prod_total) % MOD
        new_prod_minus = (-a * count) % MOD
        
        new_sum_mul = sum_total % MOD
        new_prod_mul = (prod_total * a) % MOD
        
        # Update sum_total and prod_total by combining contributions
        sum_total = (new_sum_plus + new_sum_minus + new_sum_mul) % MOD
        prod_total = (new_prod_plus + new_prod_minus + new_prod_mul) % MOD
        # Ensure prod_total is positive
        if prod_total < 0:
            prod_total += MOD
        count = (count * 3) % MOD

    result = (sum_total + prod_total) % MOD
    print(result)