program main
  implicit none
  integer*8::x,N,total,i
  integer*8,allocatable::a(:)
  integer,parameter::modulo=1000003
  data total/0/
  read *,x,N
  allocate(a(N))
  read *,a
  do i=1,N
     total = total + power(x,a(i))
  end do
  print '(i0)',MOD(total,modulo)
contains
  recursive function power(x,p) result(y)
    integer*8::x,y,p
    integer,parameter::modulo=1000003
    if(p.eq.0) then
       y = 1
       return
    end if
    y = power(mod(x*x,modulo),p/2)
    if(MOD(p,2).eq.1) y = mod(y*x,modulo)
  end function power
end program main