#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i, n) for(long long i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;

using lint = long long;
using mint = atcoder::modint;

int main() {
    int x, n;
    cin >> x >> n;
    mint::set_mod(1000003);
    mint ans = 0;
    rep(i, n) {
        int a;
        cin >> a;
        ans += mint(x).pow(a);
    }
    cout << ans.val() << endl;
}