x,n=map(int,input().split())
aa=list(map(int,input().split()))
md=1000003
ans=0
for a in aa:
    ans=(ans+pow(x,a,md))%md
print(ans)