#include<iostream>


#include<functional>
using namespace std;
#define LL long long
#define mod 1000003
inline LL powmod(LL x, int a){
	LL res = 1;
	for (int i = 0; i < 31; i++){
		if (a&(1 << i))res = (res*x) % mod;
		x = (x*x) % mod;
	}
	return res;

}
int main(void){
	LL x,res=0;
	int N;
	int a;
	cin >> x >> N;
	for (int i = 0; i < N; i++)
	{
		cin >>a;
		res = res + powmod(x, a);
	}
	cout << res%mod << endl;
	return 0;
}