X, N = gets.split.take(2).map(&:to_i)
A = gets.split.take(N).map(&:to_i)
p A.inject(0){|r,a|
  (r + X ** a) % 1_000_003
}