# -*- 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)