x, n = map(int, input().split())
a = list(map(int, input().split(" ")))
ans = 0
for i in range(n):
    ans += x**a[i]%(10**6+3)
    ans = ans%(10**6+3)
print(ans)