import sys

input = sys.stdin.readline

def main():
    x, N = map(int, input().split())
    M = 1000003
    print(sum(pow(x, int(a), M) for a in input().split())%M)

if __name__ == '__main__':
    main()