def main():
    X, N = map(int, input().split())
    A = tuple(map(int, input().split()))

    n = 0
    for a in A:
        n += pow(X, a, 1000003)
        n = n % 1000003
    print(n)

main()