x, N = map(int, input().split())
A = list(map(int, input().split()))

MOD = 1000003
answer = 0
for c in A:
	answer += pow(x, c, MOD)

print(answer % MOD)