x, N = map(int, input().split())
A = list(map(int, input().split()))
MOD = 1000003

def calc(base, exp, mod):
    res = 1
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

ans = 0
for a in A:
    temp = calc(x, a, MOD)
    ans += temp

print(ans % MOD)