fun readInt () =
    valOf (TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn)

        
fun mod_pow x n m =
    let
        fun mod_pow_aux _ 0 = 1
          | mod_pow_aux xx nn = 
            if nn mod 2 = 1 then (xx mod m) * mod_pow_aux xx (nn - 1)
            else mod_pow_aux ((xx * xx) mod m) (nn div 2)
    in
        (mod_pow_aux x n) mod m
    end


val () =
    let
        val x = Int.toLarge (readInt ())
        val n = readInt ()
        val a_s = List.tabulate (n, fn _ => Int.toLarge (readInt ()))

        val m = Int.toLarge 1000003

        val ans =
            List.foldl
                (fn (a, acc) =>
                    mod_pow x a m + acc)
                (Int.toLarge 0)
                a_s
    in
        print (LargeInt.toString ans ^ "\n")
    end