#include <bits/stdc++.h>
#define DIV 1000003 

using namespace std;

int X, N;
double kou[101] = {0};

double rec(int count = 0, double sum = 0){
    
    if(count == N) return sum;
    
    double res = 0;
    
    res = rec(count + 1, sum + fmod(pow(X, kou[count]), DIV));
    res = fmod(res, DIV);
    
    return res;
}

int main(void){
    
    cin >> X >> N;
    
    int i;
    for(i = 0; i < N; ++i){
        cin >> kou[i];
    }
    
    printf("%0.f\n", rec());
    
    return 0;
}