def getinputdata():

    array_result = []
    
    data = input()
    # 配列初期化
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

            else:

                flg = 0
    finally:

        return array_result
    
arr_data = getinputdata()

x=int(arr_data[0][0])
n=int(arr_data[0][1])

arr=[int(arr_data[1][i]) for i in range(0,n)]

mysum=0

for i in arr:
    
    mysum+=x**i
    
print(mysum % 1000003)