#include <iostream>
#include <vector>
#include <algorithm>

std::vector<unsigned long long> dp;	//dp[n] = x^(n) % Z

unsigned long long x, N;

const unsigned long long Z = 1000003;

int getRest(int a)	//x^aの余り。
{
	unsigned long long result = 1;
	
	if(dp[a] != -1)
	{
		return dp[a];
	}
	
	if(a == 0)
	{
		return 1;
	}
	
	for(int i = 1; i <= a; i ++)	//a=3:i=1,2,3
	{
		result = (result * x) % Z;
		
		dp[i] = result;
		
		if(a - i != 0 && dp[a - i] != -1)
		{	
			//std::cout << result << " " << dp[a - i] << " ";
		
			result = (result * dp[a - i]) % Z;
			
			//std::cout << "used " << a - i << " " << result << " " << dp[a - i] << std::endl;
 			
 			break;
		}
	}
	
	dp[a] = result;
	
	return result;
}

int main(void)
{
	std::cin >> x >> N;
	
	x = x % Z;
	
	std::vector<int> a(N);
	
	for(int i = 0; i < N; i ++)
	{
		std::cin >> a[i];
	}
	
	std::sort(a.begin(), a.end());
	
	dp.resize(a[N - 1] + 1);
	std::fill(dp.begin(), dp.end(), -1);
	dp[0] = 1;
	
	//mod 1000003
	
	unsigned int result = 0;
	
	for(int i = 0; i < N; i ++)
	{
		result += getRest(a[i]);
	}
	
	std::cout << result << std::endl;

	return 0;
}