x,n = map(int, raw_input().split())
l = sorted(map(int, raw_input().split()))
ret = 0
r = 1
p = 0
i = 0
while p <= l[-1]:
    if p == l[i]:
        ret += r
        i += 1
    r = (r * x) % (10**6+3)
    p += 1
print ret