def modpow(x, n, m):
    res = 1
    while(n>0):
        if((n&1)==1): res = x*res%m
        x = x*x%m
        n >>= 1
    return res

x, n = map(int, input().split())
m = 1000003
res = 0
for a in list(map(int, input().split())):
    res = (res+modpow(x, a, m))%m

print(res)