x,n = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
dp = Hash.new do |h,k|
    h[k] = (h[(k + 1) / 2] * h[k / 2]) % 1000003
end
dp[0] = 1
dp[1] = x
total = a.sort.reverse.inject(0) {|s, v|
    (s + dp[v]) % 1000003
}

puts total