x, N = map(int, input().split())
exps = map(int, input().split())

print(sum([pow(x, a, 1000003) for a in exps]) % 1000003)