x,n = map(int,input().split())
a = list(map(int,input().split()))
div = 1000003
a.sort()
xdiv = [0 for i in range(n)]
xdiv[0] = (x**a[0])%div
for i in range(1,n):
	xdiv[i] = (xdiv[i-1]*x**(a[i]-a[0]))%div
print(sum(xdiv)%div)