p = 1000003
x,N = map(int,raw_input().split())
print sum(pow(x,a,p) for a in map(int,raw_input().split())) % p