#include<iostream>
using namespace std;
typedef long long int ll;
const ll mod=1000003;

ll p(ll n,ll m)
{
	if(m==0)return 1;
	else if(m%2==0)return p(n*n%mod,m/2)%mod;
	else return ((p(n*n%mod,m/2)%mod)*n)%mod;
}

int main()
{
	int x,n;cin>>x>>n;
	ll a[100];
	for(int i=0;i<n;i++)cin>>a[i];
	ll ans=0;
	for(int i=0;i<n;i++)
	{
		ans+=p(x,a[i]);
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}