x,n = map(int,raw_input().split())
a = map(int,raw_input().split())
m = 1000003
 
sum = 0
for i in a:
	sum += pow(x,i,m)
print sum % m