x,n=map(int,input().split())
a=list(map(int,input().split()))
ans=0
mod=1000003
for i in a:
    ans+=((x**i)%mod)

print(ans%mod)