#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int mpow(ll a, ll b, ll mod) {
    ll ret = 1;
    while (b) {
        if (b&1) ret = ret * a % mod;
        a = a*a%mod;
        b >>= 1;
    }
    return ret;
}

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