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

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

main()