x,N=map(int,input().split())
A=list(map(int,input().split()))
Mod=10**6+3

S=0
for a in A:
    S+=pow(x,a,Mod)
    S%=Mod
print(S)