x, N = gets.split.map(&:to_i)
as   = gets.split.map(&:to_i)

A = 10 ** 6 + 3

ans = 0
as.each do | a |
  ans += x ** a
end
p ans % A