#include using namespace std; using ll = long long; #define rep(i, s, e) for (int i = (int)s; i < (int)e; ++i) #define all(a) (a).begin(), (a).end() ll modpow(ll a, ll n, ll m) { ll res = 1; while (n > 0) { if (n & 1) res = res * a % m; a = a * a % m; n >>= 1; } return res; } const ll mod = 1000003; int main() { cin.tie(nullptr); ll x, N; cin >> x >> N; ll ans = 0; rep(i, 0, N) { ll a; cin >> a; ans += modpow(x, a, mod); ans %= mod; } cout << ans << '\n'; }