import math._

object Main {
  def modPow(a: Long, n: Long, mod: Long): Long = {
    if (n == 0) return 1
    if (n == 1) return a % mod

    val x = modPow(a, n/2, mod)
    if (n % 2 == 0)
      (x * x) % mod
    else
      (((a * x) % mod) * x) % mod
  }

  def main(args: Array[String]) {
    val sc = new java.util.Scanner(System.in)
    val x, n = sc.nextInt

    val mod = 1000003
    var ans = 0L
    for (i <- 0 to n-1) {
      val a = sc.nextInt
      ans = (ans + modPow(x, a, mod)) % mod
    }
    println(ans)
  }
}