x,n=map(int,input().split())
a=list(map(int,input().split()))
mod=10**6+3
ans=0
for i in a:
    ans+=pow(x,i,mod)
print(ans%mod)