x,n=map(int,input().split())
A=list(map(int,input().split()))

def pow(x,n):
    ans=1
    while(n>0):
        if bin(n&1)==bin(1):
            ans=ans*x
        x=x*x
        n=n>>1
    return ans

mod=1000003
ans=0
for i in range(n):
    ans+=(pow(x,A[i]))%mod
print(ans%mod)