d=1000003;x,n,*a=$<.read.split.map &:to_i;s=0;a.map{|e|s+=x**(e%~-d)};p s%d