module mdl
    implicit none
    integer(kind=8),parameter::m=1000003
contains

    integer(kind=8) function pow(a,pwr)
        implicit none
        integer(kind=8),value::a,pwr
        pow=1
        do while(pwr>0)
            if(mod(pwr,2)==1)pow=mod(pow*a,m)
            a=mod(a*a,m)
            pwr=pwr/2
        end do
    end function
end module



program main
    use mdl
    implicit none
    integer(kind=8)::i,j,l,r,x,y,n
    integer(kind=8)::ret=0,a(100)
    read(*,*)x,n
    read*,(a(i),i=1,n)
    do i=1,n
        ret=mod(ret+pow(x,a(i)),m)
    end do
    print*,ret
end program