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