x, n = map(int, input().split())
a = list(map(int, input().split(" ")))
ans = 0
def f(c, n):
    if n == 0:
        return 1
    elif n == 1:
        return c
    else:
        if n % 2 == 0:return f(c,n//2)**2
        else: return c*f(c,n//2)**2
for i in range(n):
    ans += f(x,a[i])%(10**6+3)
print(ans)