func main()
	var _: [][]char
	do _ :: cui@input().split(" ")
	var x: int :: _[0].toInt(&)
	var N: int :: _[1].toInt(&)
	do _ :: cui@input().split(" ")
	var ans: int
	const mod: int :: 1000003
	for i(0, N - 1)
		var a: int :: _[i].toInt(&)
		do ans :: (ans + math@modPow(x, a, mod)) % mod
	end for
	do cui@print("\{ans}\n")
end func