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

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