import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static void main (String[] args) throws IOException
    {
    	Scanner sc = new Scanner(System.in);
    	int x = sc.nextInt();
    	int N = sc.nextInt();
    	
    	int a[] = new int [N+10];
    	long s[] = new long [100000002];
    	long ans = 0;
    	a[0] = 0;
    	
     	for (int i = 1 ; i <= N ; i++){
    	    a[i] = sc.nextInt();
    	}
    	
    	s[0] = 1;
    	s[1] = x;
    	for (int i=2 ;i <= 100000000 ;i++){
    		s[i] = (s[i-1] * x) % 1000003;
    	}
    	
    	for (int j=1 ; j <= N ; j++){
    		ans = (ans + s[a[j]]) % 1000003 ;
    	}
    	
    	System.out.println(ans);
    }

}