from functools  import reduce
x,N=map(int,input().split())
A=list(map(int,input().split()))
m=1000003
print(reduce(lambda a,b,M=m: (a+b)%M, map(lambda a,M=m,X=x: X**a%M, A)))