MOD = 1000003
X, N = map(int, input().split())
A = sorted(map(int, input().split()))
ans = p = pow(X, A[0], MOD)
if N >= 2:
    D = [A[i] - A[i-1] for i in range(1, N)]
    for d in D:
        p = p * pow(X, d, MOD)
        ans = (ans + p) % MOD
print(ans)