module main;

import std;

void main()
{
	immutable MOD = 1_000_003uL;
	// 入力
	ulong x, N;
	readln.chomp.formattedRead("%d %d", x, N);
	auto A = readln.split.to!(ulong[]);
	// 答えの計算
	ulong ans = 0;
	foreach (a; A)
		ans = (ans + powmod(x, a, MOD)) % MOD;
	// 答えの出力
	writeln(ans);
}