x,N=map(int,input().split())
A=list(map(int,input().split()))
mod=1000003
ANS=0
for a in A:
    ANS+=pow(x,a,mod)
    ANS%=mod
print(ANS)