#include <iostream>

using namespace std;

#define MOD 1000003

int memo[100000001];

int main(){
    int x,N;
    cin>>x>>N;

    memo[0]=1;
    for(int i=1;i<=100000000;i++){
        memo[i]=memo[i-1]*x;
        memo[i]%=MOD;
    }
    int ans=0;
    for(int i=0;i<N;i++){
        int a;
        cin>>a;
        ans +=memo[a];
        ans%=MOD;
    }

    cout<<ans<<endl;
}