x,N=map(int,input().split())
a=list(map(int,input().split()))

ans=0
mod=1000003

for i in range(N):
    ans+=pow(x,a[i],mod)
    ans%=mod
print(ans)