package main

import "fmt"

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

func pow(x, y int64) (ret int64) {
	var count uint64
	ret = 1
	for y > 0 {
		if y&1 == 1 {
			ret *= x
		}
		x = x * x
		y = y >> 1
		count++
	}
	return
}