import math

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