#include <stdio.h>

int main(void){
	// 入力された値（変数値・項の数）
	long long num, element;
	scanf("%lld%lld",&num,&element);
	// 累乗の合計
	long long ans = 0;
	// 入力された値（各項の指数値）
	long long value = 0;
	// 項の数だけループ
	for(long long i = 0;i < element;i++){
		scanf("%lld",&value);
		// 指数値の数だけループして累乗する
		long long tmp = 1;
		for(long long i = 1;i <= value;i++){
			tmp *= num;
		}
		ans += tmp;
	}
	ans = ans % 1000003;
	printf("%lld",ans);
	
}