# -*- coding: utf-8 -*-
def pow(x,i):
    if(i==0):
        return 1
    if(i==1):
        return x
    return pow(x,int(i/2))**2*pow(x,i&1)% c

x,N=list(map(int,input().split()))
lstin=list(map(int,input().split()))

c = 1000003
sum=0
for i in range(N):
    sum+=pow(x,lstin[i])
print(sum)