import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) {
	      BufferedReader stdReader =new BufferedReader(new InputStreamReader(System.in));
	      try {
	    	  String[] temp1 = stdReader.readLine().split(" ");
	    	  int x = Integer.parseInt(temp1[0]);
	    	  int N = Integer.parseInt(temp1[1]);
	    	  String[] temp2 = stdReader.readLine().split(" ");
	    	  BigInteger ans = BigInteger.valueOf(0);
	    	  for(int i=0;i<N;i++){
	    		  ans = ans.add(BigInteger.valueOf(x).pow(Integer.parseInt(temp2[i])));
	    	  }	    	  
	    	  System.out.println(ans.remainder(BigInteger.valueOf(1000003)));
	      } catch (IOException e) {
			e.printStackTrace();
	      }
	}
}