#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <list>
using namespace std;

int main(int argc, const char * argv[]) {
    long long x;
    cin >> x;
    long long N;
    cin >> N;
    long long n;
    long long div = 1000003;
    long long result = 0;
    long long tmp = x;
    long long count = 0;
    vector<long long>a;
    for (int i = 0; i < N; i++) {
        cin >> n;
        if (n != 0) {
            while(count < n - 1){
                if(tmp > div){
                    tmp %= div;
                }
                tmp *= x;
                count++;
            }
            result += tmp;
            tmp = x;
            count = 0;
        }
        else{
            result += 1;
        }
    }
    cout << result%div;
    cout << "\n";
}