d=1000003
f x 0 = 1
f x n = (x * f x (n-1))`mod`d
main=do
    [x,_]<-getLine>>=return.map(read::String->Integer).words
    a<-getLine>>=return.map(read::String->Integer).words
    print$(sum[f x n|n<-a])`mod`d