x, N = map(int, raw_input().split()) an = map(int, raw_input().split()) an.sort(reverse=True) def calc(m, i): return 1 + m * x**i m = 1 for k in xrange(N-1): i = an[k] - an[k+1] m = calc(m, i) % (10**6+3) print (m * x**an[-1]) % (10**6+3)