#include<bits/stdc++.h>

using namespace std;

long long x,n,z,ans,mod=1000003;

long long FP(){
    long long res=1,d=x;
    while(z){
        if(z&1)res=res*d%mod;
        d=d*d%mod,z>>=1;
    }
    return res;
}

int main(){
    cin>>x>>n;
    for(int i=1;i<=n;i++){
        cin>>z;
        ans=(ans+FP())%mod;
    }
    cout<<ans;
}