import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	static int mod=1000003;
	public static void main(String[] args) throws Exception {
		PrintWriter pw=new PrintWriter(System.out);
		Scanner sc=new Scanner(System.in);
		long x=sc.nextLong();
		int n=sc.nextInt();
		int a;
		int ans=0;
		for(int i=0;i<n;i++){
			a=sc.nextInt();
			ans=(int)(ans+powmod(x,a))%mod;
		}
		pw.println(ans);
		pw.close();
		sc.close();
	} 
	
	
	public static long powmod(long a,int p){
		if(p==0)return 1;
		if(p%2==1){
			return a*powmod(a,p-1)%mod;
		}
		long c=powmod(a,p/2);
		return c*c%mod;
	}

}