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

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