import java.math.*;
import java.util.*;
import java.util.stream.*;

import static java.util.stream.Collectors.*;

public class Main {
    private static final BigInteger MOD = BigInteger.valueOf(1_000_003);
    private void solve() {
        Scanner sc = new Scanner(System.in);
        BigInteger x = BigInteger.valueOf(sc.nextInt());
        sc.nextLine();
        int res = Stream.of(sc.nextLine().split(" "))
                        .map(e -> x.modPow(new BigInteger(e), MOD))
                        .reduce(BigInteger.ZERO, (p, q) -> p.add(q).mod(MOD))
                        .intValue();
        System.out.println(res);
    }

    public static void main(String[] args) {
        new Main().solve();
    }
}