def modpow(a, b, N):
    p = a
    ans = 1
    for i in range(30):
        if not b & (2**i) == 0:
            ans *= p
            ans %= N
        p *= p
        p %= N
    return ans


P = 1_000_003

x, N = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

ans = 0
for i in a:
    ans += modpow(x, i, P)
    ans %= P

print(ans)