data = input().split()
x = int(data[0])
num = int(data[1])
sum = 0
data = input().split()
for i in range(num):
	sum = (sum + pow(x,int(data[i])))%1000003
print(sum)