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

mod = 10 ** 6 + 3
ans = 0

for i in A:
    tmp = 1
    for j in range(0, i):
        tmp *= x
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans)