x,_=map(int,input().split())
a=list(map(int,input().split()))
print(sum(pow(x,ai,1000003) for ai in a)%1000003)