import java.math.*;
import java.util.*;
class A{
	static Scanner s = new Scanner(System.in);
	static final int mod = 1_000_003;
	static final BigInteger modb = BigInteger.valueOf(mod);

	public static void main(String[] args) {
		BigInteger in = BigInteger.valueOf(s.nextInt());
		s.next();
		long r = 0;
		while(s.hasNext()) {
			r += Long.parseLong(in.modPow(BigInteger.valueOf(s.nextInt()), modb).toString());
		}
		System.out.println(r%mod);
	}
}