#include <iostream>
#include <map>
using namespace std;

map<int,int> powx;

int mod = 1000003;

long long pow(int x, int n) {
    long long ret;
    if (powx.count(n))
        ret = powx[n];
    else if (n == 0)
        ret = 1;
    else if (n == 1)
        ret = x;
    else {
        ret = pow(x,n/2) * pow(x,n-n/2) % mod;
        powx[n] = ret;
    }
    return ret;
}

int main() {
    int x,n;
    cin >> x >> n;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        ans = (ans + pow(x,a)) % mod;
    }
    cout << ans << endl;
    return 0;
}