MOD = 1000003

xp = Array(Int64).new(30, 0)
xp[0] = gets.not_nil!.to_i64
n = gets.not_nil!.to_i

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

ans = 0_i64
n.times do
  a = gets.not_nil!.to_i
  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