def main():
    xn = list(map(int, input().split()))
    a = list(map(int, input().split()))

    x = xn[0]
    N = xn[1]

    sum = 0
    for i in range(N):
        sum += x ** a[i]

    print(sum % 1000003)

if __name__ == "__main__":
    main()