M = 1000003

def powmod(a, b, p):
    if b == 0:
        return 1
    if b & 1:
        return a * powmod(a, b - 1, p) % p
    return powmod(a, b // 2, p) ** 2 % p

x, n = map(int, input().split())
a = list(map(int, input().split()))
result = 0
for i in a:
    result += powmod(x, i, M)
    result %= M
print(result)