x,N = map(int,input().split())
a = sorted(list(map(int,input().split())))

fx = 0
while a:
    y = a.pop(0)
    fx += pow(x,y,1000003)
print(fx%1000003)