MOD = 1000003
x, n = map(int, raw_input().split())
print sum(map(lambda a: pow(x, int(a), MOD), raw_input().split())) % MOD