import sequtils,strutils

proc powInt(n : int64, m : int64, k = 1_000_003):int64 =
    if m == 0:
        return 1
    elif m == 1:
        return (n mod k)
    if (m mod 2) == 0:
        return powInt((n*n) mod k,m div 2, k) mod k
    else:
        return (powInt((n*n) mod k,m div 2, k) * n) mod k

var
    x,N : int
(x,N) = stdin.readline.split.map(parseInt)
var
    A = stdin.readline.split.map(parseInt)
    ans = 0.int64

for a in A:
    ans = (ans + powInt(x.int64,a.int64)) mod 1_000_003

echo ans