x, n = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
sum = 0
n.times do |i|
  sum += x ** a[i]
end
puts sum % 1000003