x,N=map(int,input().split())
a=list(map(int,input().split()))
sum=0
mod=1000003
for i in range (N):
    sum+=(x**a[i]%mod)
print(sum)