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

for i in range(n):
    ans += pow(x,a[i],mod)
    ans %= mod
print(ans)