x, cnt = map(int,input().split())
ans = 0
a = list(int(i) for i in input().split())
for i in a:
    ans += pow(x,i)
print(ans%1000003)