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