x, n = map(int, input().split())
print(sum(x ** i for i in map(int, input().split())) % 1000003)