問題文

Maliaは、与えられた数式を計算しようとしている。
数式は一つの変数$x$のみで構成されており、各$i$項は$x$の$a_i$乗で構成されている。
ここで $x^n$は$x$の$n$乗を表すことにすると
$x^{a_1}+x^{a_2}+\cdots +x^{a_N}$
という形になっている。
$x$の累乗を計算するのは大変だと気づいたあなたは、代わりに計算してあげることになりました。

$x$と各$a_i(1\le i\le n)$が与えられた時の計算値を求めてください。
答えの値が非常に大きくなるので計算値に対して$1,000,003$ で割ったあまりを求めてください。

計算途中の値が32ビットに収まらないことが有ります。

入力

$xN$
$a_1{a}_2\dots a_N$

$1$行目に変数値を表す整数値$x(1\le x\le 100)$と項の数を表す整数値$N(1\le N\le 100)$が半角スペース区切りで与えられる。
$2$行目には、各項の指数値を表す整数値 $a_i(0\le a_i\le 100,000,000)$が半角スペース区切りで与えられる。

出力

$x^{a_1}+x^{a_2}+\cdots +x^{a_N}$ の計算値を $1,000,003$ で割ったあまりを求めてください。

サンプル

2 3
1 2 3

14

2 2
0 100

253110