import sys
read = sys.stdin.buffer.read

MOD=1_000_003
x,N,*A=map(int, read().split())
ANS=sum(pow(x,ai,MOD)for ai in A)%MOD
print(ANS)