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);}}