X, N = map(int, input().split())
MOD = 1000003
f = lambda a: pow(X, int(a), MOD)
print(sum(map(f, input().split())) % MOD)