M = 1000003
x, N = [int(s) for s in input().split()]
pa = [int(s) for s in input().split()]
pb = [pow(x,y,M) for y in pa]
print(sum(pb)%M)