b, n = map(int,input().split())
ls = list(map(int,input().split()))

sm = 0
for i in ls:
    sm += b**i%1000003
print(sm%1000003)