import sys
input=lambda: sys.stdin.readline().rstrip()
x,n=map(int,input().split())
A=[int(i) for i in input().split()]
mod=10**6+3
ans=0
for a in A:
  ans=(ans+pow(x,a,mod))%mod
print(ans)