x, N = map(int,input().split())
res = 0
m = 1000003
for i in map(int,input().split()):
    res += pow(x,i,m)
print(res%m)