#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 = 1;i <= element;i++){
		scanf("%lld",&value);
		// 指数値の数だけループして累乗する
		long long tmp = 0;
		if(value == 0){
			tmp = 1;
		}else{
			for(long long i = 1;i <= value;i++){
				tmp *= i;
			}	
		}
		ans += tmp;
	}
	printf("%lld",ans %= 1000003);
	
}