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