x, N=map(int, raw_input().split())
a=map(int, raw_input().split())
s=0


for i in a:
    s+=pow(x, i, 1000003)


print s%1000003