x, N = map(int,input().split())
log = list(map(int,input().split()))
log.sort()
res = 0
p = 1
for i,v in enumerate(log):
    if i == 0:
        a = v
    else:
        a = v - pv
    pv = v
    p *= x**a
    res += p
print(int(res%1000003))