MOD = 1000003
mem = {}
X, N = map(int, raw_input().split())
a = map(int, raw_input().split())

def power(x, n):
    if n in mem:
        return mem[(x, n)]
    if n == 0:
        return 1
    if n%2 == 0:
        mem[(x, n)] = power(x*x, n/2) % MOD
    else:
        mem[(x, n)] = x * power(x, n-1) % MOD
    return mem[(x, n)]

print sum(map(lambda n:power(X, n), a))