x, n = gets.split(' ').map(&:to_i)
a = gets.split(' ').map(&:to_i)
puts a.map{|an| x ** an}.inject(:+) % 1_000_003