x,n = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
dp = (0..100).to_a
dp[0] = 1
dp[1] = x
(2..100).each do |i|
    dp[i] = dp[(i + 1) / 2] * dp[i / 2] % 1000003
end
total = a.inject(0) {|s, v|
    (s + dp[v]) % 1000003
}
puts total