#include <iostream>
using namespace std;

#define MOD(N) ((N) % 1000003)
#define FOR(i,s,e) for(int i = (s);i <= (e);i++)

int dp[100000000];

int N;
int x;

int max_ = 0;

int a[100];

int main()
{
	cin >> x >> N;
	FOR(i,0,N -1)
	{
		cin >> a[i];
		max_ = max(max_,a[i]);
	}
	dp[0] = 1;
	FOR(i,1,max_)
	{
		dp[i] = MOD(dp[i - 1] * x);
	}
	int res = 0;
	FOR(i,0,N-1)
	{
		res = MOD(res + dp[a[i]]);
	}
	cout << res << endl;
	return 0;
	
}