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


for i in a:
    s+=x**i


print s%1000003