import strutils
import sequtils

const Mod : int = 1_000_003

proc powMod (n : int, x : int, m : int) : int =
  if n == 1: return 1
  if x == 0: return 1
  if x mod 2 == 0:
    return powMod(n, x div 2, m) * powMod(n, x div 2, m) mod m
  else:
    return n * powMod(n, x div 2, m) * powMod(n, x div 2, m) mod m

var xn = stdin.readLine.split.map(parseInt)
var A = stdin.readLine.split.map(parseInt)
var (x, _) = (xn[0], xn[1])
var ans = 0
for a in A:
  ans += powMod(x, a, Mod)
  ans = ans mod Mod
echo ans