x , n = map(int, input().split())
a = map(int, input().split())

c = 0

for i in a:
	c += x ** i

print(c % 1000003)