import math
input_data = input()
input_s = input_data.split(" ")
base_d = int(input_s[0])
n_d = int(input_s[1])

second_d = input()
second_s = second_d.split(" ")
result = 0
temp_data=0
temp_result=0

for n_num in range(n_d):
	temp_data = int(second_s[n_num])
	temp_result = int(math.pow(base_d,temp_data))%1000003
	result = result + temp_result

print(result)