No.16 累乗の加算
yuki2006問題文
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\)となる。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。