import java.util.Scanner;

public class yukicoder_16 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int x = scanner.nextInt();
		int n = scanner.nextInt();
		
		long[] a = new long[n];
		
		for (int i = 0; i < n; i++) {
			a[i] = scanner.nextLong();
		}
		
		long sum = 0;
		for (int j = 0; j < n; j++) {
			sum += Math.pow(x, a[j]);
		}
		
		long extra = sum % 1000003;
		
		System.out.println(extra);
	}
}