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