x, n = map(int,input().split())
a = list(map(int, input().split()))

mod = 1000003

total = 0
for ai in a:
    total += pow(x, ai, mod)

print(total % mod)