x=int(input().split()[0])
print(sum(x**int(s)%1000003 for i,s in enumerate(input().split()))%1000003)