input_values = map(int, open(0).read().split())
x = next(input_values)
next(input_values)
a = list(input_values)
M = 10**6 + 3
result = sum(pow(x, k, M) for k in a) % M
print(result)