x, N = map(int, input().split())
a = list(map(int, input().split()))
n = 1000003
result = 0

for i in range(N):
    result += pow(x, a[i], n)
    result = result % n

print(result)