x, _ = [int(i) for i in input().strip().split(" ")]
mod = 1000003
print(sum([pow(x,int(i),mod) for i in input().strip().split(" ")]) % mod)