#include <atcoder/modint>
#include <iostream>
#include <vector>

int main() {
    using namespace std;
    constexpr int MOD = 1000003;
    using mint = atcoder::static_modint<MOD>;
    int x0, n;
    cin >> x0 >> n;
    mint ans = 0, x = x0;
    while (n--) {
        int a;
        cin >> a;
        ans += x.pow(a);
    }
    cout << ans.val() << endl;
}