X,N=gets.split.map(&:to_i)
A=gets.split.map(&:to_i)
MOD=10**6+3

puts A.map{|a|X.pow(a,MOD)}.sum%MOD