# frozen_string_literal: true

LAW = 10**6 + 3

X, N = gets.chomp.split.map(&:to_i)
AS = gets.chomp.split.map(&:to_i)

MAX_A = AS.max

EXPONENTS = MAX_A.times.each_with_object([1]) do |_i, a|
  a << a.last * X
end

RESULT = AS.map { |i| EXPONENTS[i] % LAW }.sum % LAW

puts RESULT