x,N=map(int,input().split())
A=list(map(int,input().split()))
mod=10**6+3
print(sum([pow(x, a, mod) for a in A])%mod)