def func(x,a,d):
    if a == 0:
        return 1
    elif a == 1:
        return x % d
    else:
        r = func(x,a/2,d)
        r = r*r if a % 2 == 0 else r*r*(x%d)
        return r % d

x,n = map(int, raw_input().split())
l = map(int, raw_input().split())
ret = 0
for a in l:
    ret += func(x,a,(10**6+3))
print ret % (10**6+3)