!>
!! @brief 剰余演算(modular arthmeric)に関するアルゴリズムを扱う
!!
!! @note  剰余演算は、おおよそ、通常の整数上の演算とつぎの点を除けば同じであると考えてよい. すわなち、nを法とする剰余演算では、
!!        すべての結果xはn、を法としてxと等しい{0, 1, ..., n-1}の要素と置き換える. 加算、減算、乗算だけしか扱わなければ、
!!        この簡略な説明で十分である. 剰余演算の正確なモデルは群論の枠組みで記述するのが最善である
!!
!! @date  2016/05/07 
!!


module module_modular
  implicit none
  
  public :: modpow

contains

  !>
  !! @brief 反復2乗法(repeated squaring)によるべき乗剰余(modular exponetiation)の計算を扱います
  !!
  !! @note  Fortranでは引数は参照渡しとなるので非負整数a, bに対して破壊的代入を行うと面倒なことになる
  !!        そこで今回は再帰で反復2乗法を書くことにした
  !!
  recursive function modpow(a, b, n) result(d)
    implicit none

    integer(8), intent(in)  :: a, b, n
    integer(8) :: d

    if (b .eq. 0) then  ! 再帰の基底
       d = 1
       return
    end if

    d = modpow(mod(a * a, n), b / 2, n)
    ! bが偶数の場合、d^b = ((d^2)^(b/2))であるから、n/2の場合に帰着できる
    
    if (iand(b, 1) .eq. 1) then  ! bが奇数の場合、
       d = mod((d * a), n)       ! d^b = ((d^2)^(b/2)) * aであるから、n/2の場合に帰着できる
    end if
  end function modpow
  
  
end module module_modular

program main
  use module_modular
  implicit none

  integer(8) :: output, b, x, n, i
  integer(8), parameter :: m = 1000003
  character(9500)  input, output2
  character(100)   output1
  character(10), parameter :: delim = " "

  read(*,*) x, n  
  read(*, '(a)') input

  
  output = 0
  do i = 1, n
     call split(input, output1, output2, delim)
     input = output2

     read(output1, *) b 
     output = output + modpow(x, b, m)
     output = mod(output, m)
  end do
  
  write(*, '(I0)') output
contains

  
  subroutine split(input, output1, output2, delim)
    implicit none
    
    character(*), intent(inout) :: input
    character(*),  intent(out)  :: output1
    character(*), intent(out)   :: output2
    character(*),   intent(in)  :: delim
    integer :: index

    input = trim(input)

    index   = scan(input, delim)
    output1 = input(1:index-1)
    output2 = input(index+1:)
  end subroutine split
  
end program main