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