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])
    
print(ans % 1000003)