P = 1000003

x, N = map(int, input().split())

ans = 0

for a in map(int, input().split()):
    
    ans += pow(x, a % (P - 1), P)
    
    ans %= P
    
print(ans)