x, n = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

M = 1000003
mod = Array.new(a[-1])
mod[0] = 1
mod[1] = x % M
2.upto(a[-1]) do |i|
  mod[i] = (mod[i-1] * mod[1]) % M
end

puts a.map{|ai| mod[ai] }.inject(:+) % M