MOD = 1000003

input = gets.not_nil!.split
xp0 = input[0].to_i64
n = input[1].to_i

xp = Array(Int64).new(30, 0)
xp[0] = xp0

# Precompute xp powers
(1...30).each do |i|
  xp[i] = (xp[i-1] * xp[i-1]) % MOD
end

ans = 0_i64
numbers = gets.not_nil!.split.map(&.to_i)
numbers.each do |a|
  r = 1_i64
  30.times do |j|
    if (a >> j) & 1 == 1
      r = (r * xp[j]) % MOD
    end
  end
  ans = (ans + r) % MOD
end

puts ans