x,n=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
sum=0
for i in a: sum+=x**i
print(sum%1000003)