def f(a, b)
  case b
  when 0; 1
  when 1; a
  else
    c, d = b.divmod(2)
    f(a * a % MOD, c) * f(a, d)
  end
end

X, N = gets.split.take(2).map(&:to_i)
A = gets.split.take(N).map(&:to_i)
MOD = 1_000_003
p A.map{|a| f(X, a) }.sum % MOD