import java.math.BigDecimal;
import java.util.Scanner;
import java.util.InputMismatchException;

public class AdditionOfPowers {
    public static void main(String[] args){
        int[] N =Input();
        Processing(N);
        BigDecimal Count = BigDecimal.ZERO;
        for(int i = 0 ; i < N.length - 2 ; i++){
            Count = Count.add(Processing(N)[i]);
        }
        System.out.println(Count);
    }

    //数値を入力して範囲が正しいかを判定するメソッド
    public static int[] Input(){
        Scanner scanner = new Scanner(System.in);
        int X = scanner.nextInt();
        int N = scanner.nextInt();
        int[] Store = new int[N + 2];
        Store[0] = X;
        Store[1] = N;
        try{
        //Xの条件判定
        if(X < 1 || X > 100){
            System.out.println("Xは1以上100以下の数字で入力してください");
            System.exit(0);
        }
        //Nの条件判定
        if(N < 1 || N > 100){
            System.out.println("Nは1以上100以下の数字で入力してください");
            System.exit(0);
        }
        //各項の入力と条件判定
        for(int i = 2 ; i < N + 2 ; i++){
            int Z = scanner.nextInt();
            Store[i] = Z;
            if(Z < 0 || Z > Math.pow(10,8)){
                System.out.println("各項は0以上10000000以下で入力してください");
                System.exit(0);
            }
        }
        }catch(InputMismatchException e){
            System.out.println("数字を入力してください");
            System.exit(0);
        }catch(Exception E){
            System.out.println("想定外のエラーです");
        }
        return Store;
    }
    
    //計算を実行するメソッド
    public static BigDecimal[] Processing(int[] Store){
        int X = Store[0];
        int N = Store[1];
        BigDecimal Sum = BigDecimal.ZERO ;
        BigDecimal[] ans = new BigDecimal[N];
        int[] NewStore = new int[N];
        BigDecimal big1 = BigDecimal.valueOf(1000003);
        
        //新しい配列に旧配列を代入するループ
        for(int i = 0 ; i < N ; i++){
            NewStore[i] = Store[i + 2];
        }
        //ans配列に各項の累乗値を代入させるループ
        for(int j = 0 ; j < N ; j++){
            ans[j] = BigDecimal.valueOf(X).pow(NewStore[j]).remainder(big1);
        } 
        
        return ans;
    }
}