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

for l_i in l:
    ans += pow(x,l_i,1000003)

print(ans%1000003)