x, N = map(int, raw_input().split())
a = map(int, raw_input().split())
p = [1 for i in xrange(101)]
for i in xrange(1, 101):
    p[i] = (p[i-1] * x) % 1000003
print sum(p[i] for i in a)