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%m)**(i%m))%m)
print(s%m)