x, num  = gets.split.map(&:to_i)
arr     = gets.split.map(&:to_i)
sum = 0
arr.each { |i| sum += x ** i }
puts sum % 1000003