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

ll x, N;

ll Pow(ll a,ll b){
    ll res = 1;
    while(b){
        if(b % 2) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

int main(void){
    
    cin >> x >> N;
    
    ll sum = 0, n;
    for(ll i = 0; i < N; ++i){
        cin >> n;
        sum += Pow(x, n);
        sum %= MOD;
    }
    
    cout << sum << endl;
    
    return 0;
}