def exps_input(exps):
    return [int(e) for e in exps.split(' ')]


def pow_2(x, n):
    if n < 0:
        return pow(1 / x, -n)
    if n is 0:
        return 1
    if n % 2 is 0:
        return pow_2(x ** 2, n // 2)
    else:
        return x * pow_2(x, n - 1)


sum = 0
mod = 1_000_003
base = int(input().split(' ')[0])
for exp in exps_input(input()):
    sum += pow_2(base, exp)

print(sum % mod)