x,N=map(int,raw_input().split())
A = map(int,raw_input().split())

ans = 0
mod =1000003
for a in A:
   val=1
   curX=x
   for i in range(32):
      if (a&(1<<i))!=0:
         val *= curX
         val %= mod
      curX *= curX
      curX %= mod
   ans += val
   ans %= mod
print ans