import static java.math.BigInteger.*;
import java.math.*;
import java.util.*;
class A{
Scanner s=new Scanner(System.in);
int mod=1000003;
BigInteger modb=valueOf(this.mod);
public static void main(String[] args){
Scanner s=new Scanner(System.in);
int mod=1000003;
BigInteger modb=valueOf(mod),in=valueOf(s.nextInt());
s.next();
long r=0;
while(s.hasNext()){
r+=Long.parseLong(in.modPow(valueOf(s.nextInt()),modb).toString());
}
System.out.println(r%mod);
}
}