MOD = 1000003
x, N = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    ans = (ans + pow(x, A[i], MOD)) % MOD
print(ans)