M=1000003
x=int(raw_input().split()[0])
print sum(pow(x,int(a),M)for a in raw_input().split())%M