m = 1000003
x, N = map(int,input().split())
A = list(map(int,input().split()))
print (sum(pow(x, a, m) for a in A) % m)