import java.util.*;
 

public class Main {
	static long kuri(long x,long a){
		if(a==0) return 1;
		long res = kuri(x*x%1000003,a/2);
		if(a%2==1) res=res*x;
		return res%1000003;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextLong();
		long n = sc.nextLong();
		long ans=0;
		for(int i=0;i<n;i++){
			int aa=sc.nextInt();
			long temp=kuri(x,aa);
			ans+=temp%1000003;
		}
		System.out.println(ans%1000003);
	}
}