ss = input().split()
x = int(ss[0])
n = int(ss[1])
a = list(map(int,input().split()))
ans = 0
for i in a:
    ans += pow(x,i,1000003)
print(ans % 1000003)