x, N = map(int, raw_input().split())
n = map(int, raw_input().split())
f = 1000003
tot = 0
for i in n:
    tot += pow(x, i, f)
print tot % f