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

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

print(total)