x, n = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
mod = 10**6 + 3
ans = 0

a.each do |e|
  ans += x.pow(e, mod)
  ans %= mod
end

puts ans