x, n = [int(s) for s in input().split(' ')]
lists = [int(s) for s in input().split(' ')]

num = 0
for i in lists:
    num += (x ** i) % 1000003

print(num % 1000003)