import java.util.Scanner; public class yukicoder_16 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int x = scanner.nextInt(); int n = scanner.nextInt(); long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextLong(); } long sum = 0; for (int j = 0; j < n; j++) { sum += Math.pow(x, a[j]); } long extra = sum % 1000003; System.out.println(extra); } }