#include<bits/stdc++.h>
using lint=long long;
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    std::cout.setf(std::ios_base::fixed);std::cout.precision(15);
    lint mod=1'000'003;
    auto pow=[&](lint x,lint y){
        lint ans=1;
        for(;y;y/=2){
            if(y%2)ans=ans*x%mod;
            x=x*x%mod;
        }
        return ans;
    };
    lint x,n;std::cin>>x>>n;
    lint ans=0;
    while(n--){
        lint a;std::cin>>a;
        ans+=pow(x,a);
        if(mod<=ans)ans-=mod;
    }
    std::cout<<ans<<'\n';
}