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