def mpow(x, b, m):
    ret = 1
    while(b > 0):
        if b & 1 == 1:
            ret *= x
            ret %= m
        x *= x
        x %= m
        b >>= 1
    return ret

x, n = map(int, input().split())
a = list(map(int, input().split()))
mod = 1000003
goukei = 0

for i in a:
    goukei += mpow(x, i, mod)
    goukei %= mod
print(goukei)