package Re;

import java.util.Scanner;
import java.util.ArrayList;

public class Re_AdditionOfPower{
    public static void main(String[] args){
        ArrayList<Long> Count = Input();
        long X = Count.get(0);
        long N = Count.get(1);
        Count.remove(0);
        Count.remove(0);
        
        long Answer = Processing(X,N,Count);
        System.out.println(Answer);
    }
    
    public static ArrayList<Long> Input(){
        Scanner scanner = new Scanner(System.in);
        long X = scanner.nextLong();
        long N = scanner.nextLong();
        ArrayList<Long> Count = new ArrayList<>();
        Count.add(X);
        Count.add(N);
        for(int i = 0 ; i < N ; i++){
            long A = scanner.nextLong();
                Count.add(A);
                if(A < 0 || A > Math.pow(10,8)){
                    System.out.println("各項は0以上100000000以下で入力してください");
                    System.exit(0);
                }
        }
        
        try{
            if(X < 1 || X > 100){
                System.out.println("Xは１以上１００以下で入力してください");
                System.exit(0);
            }
            if(N < 1 || N > 100){
                System.out.println("Nは１以上１００以下で入力してください");
                System.exit(0);
            }
        }catch(Exception E){
            System.out.println("想定外のエラーです");
            System.exit(0);
        }
        return Count;
    }
    
    public static long Processing(long X ,long N,ArrayList<Long> Count){
        final long MOD = 1000003;
        long Answer = 0;
        if(X == 1){
            return 1;
        }else{
            for(int i = 0 ; i < N ; i++){
            Answer += Math.pow(X, Count.get(i)) % MOD;
            }
        }
        return Answer;
    }
}