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 += pow(x,i,m)
print(s%m)