M = 1000003
x, N = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
def f(i, x)
  t = i
  y = 1
  z = x
  while t > 0
    if t % 2 == 1
      y = (y * z) % M
    end
    z = (z * z) % M
    t /= 2
  end
  y
end
ans = a.map {|i| f(i, x)}.inject(:+) % M
puts ans