x,n=map(int,input().split())
A=list(map(int,input().split()))
y,b=0,1000003
for a in A:y+=pow(x,a,b)
print(y%b)