x, n = gets.chomp.split(" ").map(&:to_i)
a = gets.chomp.split(" ").map(&:to_i)
ans = 0
a.each do |d|
  ans += x**d
end
puts ans%1000003