x, N = map(int, input().split())
power = [int(n) for n in input().split()]

def calc(i, p):
    ans = 0
    for n in p:
        ans += pow(i, n, 1000003)
    return ans

print(calc(x, power)%1000003)