import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long ans = 0;
		
		int x = scan.nextInt();
		int N = scan.nextInt();
		for(int i=0; i<N; i++) {
			int a = scan.nextInt();
			ans += pow(x,a);
		}
		System.out.println(ans);	
	}
	
	static int pow(int x, int a) {
		int v = 1;
		for(int i=0; i<a; i++) {
			v = (v * x) % 1000003;
		}
		return v;
	}
}