import java.util.Scanner;

/**
 * yukicoder no.17
 * @author scache
 *
 */
public class PowAddition {
	public static void main(String[] args) {
		PowAddition p = new PowAddition();
	}

	public PowAddition() {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextLong();
		int n = sc.nextInt();
		long[] a = new long[n];
		for(int i=0;i<n;i++)
			a[i] = sc.nextLong();
		solve(x, a);
	}

	public void solve(long x, long[] a) {
		long res = 0;
		for(int i=0;i<a.length;i++){
			res += powMod(x, a[i]);
			res %= 1000003;
		}
		System.out.println(res);
	}
	
	public long powMod(long x, long a){
		long c = x;
		long res = 1;
		while(a>0){
			if((a&1)==1)
				res = (res*c)%1000003;
			c = (c*c)%1000003;
			a = a>>1;
		}
		return res;
	}
	
	
	// フェルマーの小定理を使う方法
//	#include <iostream>
//	#include <algorithm>
//	using namespace std;
//	#define REP(i, n) for(int(i)=0;(i)<(n);++(i))
//	typedef unsigned long long ull;
//	int x, N, a, MOD = 1000003;
//	ull res;
//	int n[1000003];
//	 
//	int main(){
//	    cin >> x >> N;
//	    n[0] = 1;
//	    REP(i,MOD) n[i+1] = (n[i] * x) % MOD;
//	    REP(i,N){ cin >> a; res += n[a%(MOD-1)]; }
//	    cout << res%MOD << endl;
//	    return 0;
//	}
}