package main

import (
	"fmt"
	"math"
)

func main() {
	var x, a float64
	var N, ans, i int64
	fmt.Scan(&x, &N)
	for i = 0; i < N; i++ {
		fmt.Scan(&a)
		ans += int64(math.Pow(x, a)) % 1000003
	}
	fmt.Println(ans)
}