def pow(x,i):
    if(i==0):
        return 1
    if(i==1):
        return x
    return pow(x,int(i/2))**2*pow(x,i&1)

x,N=list(map(int,input().split()))
lstin=list(map(int,input().split()))

sum=0
for i in range(N):
    sum+=pow(x,lstin[i])
    sum%=1000003
print(sum)