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

for i in range(n):
    s = (x ** a[i]) % mod
    goukei += s

print(goukei)