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

sum=0
for i in range(N):
    sum+=x**a[i]
    if(sum>=1000003):
        sum%=1000003
print(sum)