MOD=1000003 ans=0 x,N=map(int,input().split()) a=list(map(int,input().split())) for i in range(N): bat=1 for j in range(a[i]): bat=bat*x bat=bat%MOD ans+=bat ans=ans%MOD print(ans)