X,N=map(int,input().split())
M=1000003
print(sum(map(lambda a:pow(X,int(a),M),input().split()))%M)