x, n = map(int, input().split())
a = list(map(int, input().split()))
mod = 1000003
goukei = 0

for i in range(n):
    k = 1
    for _ in range(a[i]):
        k = (k % mod) * (x % mod)
    goukei += k % mod
print(goukei)