def main
  x, n = gets.split.map(&:to_i)
  a_list = gets.split.map(&:to_i)
  total = 0
  a_list.each do |i|
    total += 2 ** i
  end
  total % 1000003
end

p main