class Integer
  def mod_pow(n, mod)
    x = self
    res = 1

    while n > 0
      res = res * x % mod if n[0] == 1
      x = x * x % mod
      n >>= 1
    end

    res
  end
end

X, N = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
MOD = 10 ** 6 + 3

puts A.map { |a| X.mod_pow(a, MOD) }.sum % MOD