#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    long long x,n,a,ans = 0,tx;
    cin >> x >> n;

    
    for(int i = 0; i < n; i++){
        cin >> a;
        if(a == 0) ans++;
        else{
            tx = x;
            for(int i = 1; i < a; i++){
                tx *= x;
                if(tx > 1000003) tx %= 1000003;
            }
            ans += tx;
            if(ans > 1000003) ans %= 1000003;
        }
    }

    cout << ans << endl;

    return 0;
}