def power(base, exp, op=lambda x, y: x * y, ie=1):
    res = ie
    while exp:
        if exp & 1:
            res = op(res, base)
        base = op(base, base)
        exp >>= 1
    return res

x, N = map(int, input().split())
A = list(map(int, input().split()))

op = lambda x, y: x * y % 1000003
ans = 0

for i in range(N):
    ans += power(x, A[i], op, 1)

ans %= 1000003

print(ans)