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