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

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

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