x, N = map(int, input().split())
l = list(map(int, input().split()))
ans = 0

for l_i in l:
    ans += x**l_i

print(ans%1000003)