read x n
read -aa
for((m=1000003;n--;y=x,z=1,b=a[n],s+=p)){
p=b?b%2?z=z*y%m:0,y=y*y%m,b/=2,p:z
}
echo $[s%m]