#include <bits/stdc++.h>
using namespace std;

template <typename T> T modpow(T a, T b, T p)
{
	T ans = 1;
	while(b > 0)
	{
		if(b & 1) ans = ans * a % p; //bの最下位bitが1ならa^(2^i)をかける
		a = a * a % p;
		b >>= 1; //bを1bit右にシフト
	}
	return ans;
}

int main()
{
	int64_t x, n;
	cin >> x >> n;
	const int64_t mod = 1000003;
	int64_t ans = 0;
	int64_t a;
	for(int64_t i = 0; i < n; i++)
	{
		cin >> a;
		ans += modpow(x, a, mod);
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}