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