No.16 累乗の加算

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 282
作問者 : yuki2006yuki2006

2 ProblemId : 42 / 出題時の順位表

問題文

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

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

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

入力

\(x\ N\)
\(a_1\ a_2\ \dots\ a_N\)

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

出力

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

サンプル

サンプル1
入力
2 3
1 2 3
出力
14

\(x + x^2 + x^3 , x=2\) を表しております。なのでこの計算値はこのようになります。
\(x + x^2 + x^3 = 2 + 4 + 8 = 14\)

サンプル2
入力
2 2
0 100
出力
253110

\(x^0 + x^{100} = 1 + 1267650600228229401496703205376 = 1267650600228229401496703205377\)
となるが、\(1,000,003\) で割ったあまりは、\(253110\)となる。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。