def pow x,n
    ans=1
    e=x
    while n>0
        ans=(ans*e)%1000003 if n&1>0
        n/=2
        e=(e*e)%1000003
    end
    ans
end

x=gets.split[0].to_i
p gets.split.map{|s|pow x,s.to_i}.inject(:+)