def transtwo(a):
    return format(int(a), 'b')

x, N = map(int, input().split())
l = list(map(transtwo, input().split()))
ans = 0
ans1 = 1
ans_l = [x]

for i in range(len(l[-1]) - 1):
    ans_l.append(ans_l[-1]**2)


for l_i in l:
    letter_l = list(l_i)
    letter_l.reverse()
    ans1 = 1
    for i, ll_i in enumerate(letter_l):
        if ll_i == "1":
            ans1 *= ans_l[i] 
    ans += ans1
    


print(ans%1000003)