#int(input())
#map(int, input().split())
#list(map(int, input().split()))

x, N = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 6 + 3

d = [1] * (mod+1)

for i in range(mod):
    d[i+1] = (d[i] * x) % mod
    if d[i+1] == 1:
        l = i+1

ans = 0
for i in range(N):
    u, v = divmod(a[i], l)
    ans = (ans + d[v]) % mod

print(ans)