import java.math.BigDecimal

fun main(args: Array<String>) { 
  val base = BigDecimal(readLine()!!.split(" ")[0])
  val ans  = readLine()!!.split(" ").map { x -> 
    x.toInt()
  }.map { x ->
    val powed = base.pow(x)
    powed.rem(BigDecimal("1000003")) 
  }.reduce { e, x ->
    e.add(x)
  }
  println(ans)
}