x,N = map(int , raw_input().split())

def mod_pow(x, n, mod):
    res = 1
    while (n):
        if (n % 2 == 1):
            res = res * x % mod
        x = (x * x) % mod
        n /= 2
    return res
a = map(int, raw_input().split())
ans = 0
for i in range(N):
    ans += mod_pow(x, a[i], 1000003)
print ans