#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 = 0;
		for(long long i = 0;i < value;i++){
			tmp *= i;
		}
		ans += tmp;
	}
	printf("%lld",ans %= 1000003);
	
}