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