import math

if __name__ == "__main__":
    x, n = map(int, input().split(" "))
    ans = 0
    for i in list(map(int, input().split(" "))):
        if i % 2 == 1:
            i -= 1
        ans += math.pow(math.pow(x, 2), i // 2) % 1000003
    print(int(ans % 1000003))