x, N = map(int, input().split())
a = list(map(int, input().split()))
MOD = 1000003
total = 0
for exponent in a:
    total = (total + pow(x, exponent, MOD)) % MOD
print(total)