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
	for y > 0 {
		tmp := y & 1
		ret += tmp * (x << count)
		y = y >> 1
		count++
	}
	return
}