x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
l = list()
l.append(1)
for j in range(100000000):
    j+=1
    l.append(l[j - 1] * x[0] % 1000003)
ret = 0
for i in range(x[1]):
    ret += l[a[i]]
    i+=1
print(ret)