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

using namespace std;

int X, N;

long long rec(long long x, long long n){
    if(n == 0) return 1;
    if(n % 2 == 0) return rec(x * x % DIV, n / 2);
    else return x * rec(x, n - 1) % DIV;
}

int main(void){
    
    cin >> X >> N;
    
    int i, j;
    long long result = 0;
    for(i = 0; i < N; ++i){
        
        cin >> j;
        result += rec(X, j);
        
    }
    
    cout << result % DIV << endl;
    
    return 0;
}