x,N = map(int,raw_input().split())
a = map(int,raw_input().split())
ans = 0
for i in range(N):
	xx = 1
	for j in range(a[i]):
		xx *= x
	ans += xx
	ans %= 1000003
print ans