# frozen_string_literal: true

LAW = 10**6 + 3

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

MIN_A = AS.min
RESULT = ((X**MIN_A) % LAW *
          AS.map { |i| X**(i - MIN_A) % LAW }.sum % LAW) % LAW

puts RESULT