#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define INF 		2000000007
#define MOD			1000003

#define REP(i,n)	for(int i=0;i<n;++i)

typedef unsigned long long int ull;

int main(){
	int x,N;
	scanf("%d %d",&x,&N);

	vector<ull> a(N);
	for(int i=0;i<N;++i)
		cin >> a[i];//*/

	int suml=0;

	for(int i=0;i<N;++i){
		int y = 1;
		for(int j=0;j<a[i];++j){
			y = (y*x)%MOD;
		}
		suml += y;
	}

	cout << suml << endl;

	return 0;
}