$mod = 1000003

def pow(a,b)
  if b==0; return 1; end
  t = pow(a,b/2)
  return b.odd? ? a*t*t%$mod : t*t%$mod
end

ans = 0
x,n = gets.split.map(&:to_i)
gets.split.map(&:to_i).each do |a|
  ans = (ans + pow(x,a)) % $mod
end

puts ans