x,N = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
ans = 0
for i in range(N):
    ans += x**a[i]
print(ans%1000003)