N = gets.chop.to_i
a = gets.chop.split.map(&:to_i)

if N == 1
  puts a[0]
end
MOD = 10e9 + 1

def calcComb(a, b)
  return calcComb(a, a - b) if a - b < b

  (a - b + 1..a).to_a.inject(1, &:*) / (1..b).to_a.inject(1, &:*)
end

ans = 0
for i in 1..N
  ans += a[i - 1] * (calcComb(N - 1, i - 1) % MOD)
end
puts (ans % MOD).to_i