mod = 1000003
x, N = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
minA = min(A)
x0 = (x**minA)%mod
ans = 0
for a in A:
    x0 *= x**(a-minA)
    ans += x0
    ans %= mod
print(ans)