No.16 Sum of Powers
タグ : / 解いたユーザー数 608
作問者 :
yuki2006
Problem Statement
Malia is trying to evaluate a given expression.
The expression consists of only one variable \(x\), and each \(i\)-th term is \(x\) raised to the power \(a_i\).
Writing \(x^n\) for \(x\) raised to the power \(n\), the expression has the form
\( x^{a_1} + x^{a_2} + \dots + x^{a_N} \)
.
Realizing that computing powers of \(x\) is hard work, you have decided to do the calculation for her.
Given \(x\) and each \(a_i\ (1 \leq i \leq n)\), find the value of the expression.
Since the answer can be very large, find the value modulo \(1,000,003\).
Intermediate values may not fit in 32 bits.
Input
\(x\ N\) \(a_1\ a_2\ \dots\ a_N\)
The \(1\)st line contains an integer \(x\ (1 \leq x \leq 100)\) representing the value of the variable and an integer \(N\ (1 \leq N \leq 100)\) representing the number of terms, separated by a single-byte space.
The \(2\)nd line contains integers \(a_i\ (0 \leq a_i \leq 100,000,000)\) representing the exponent of each term, separated by single-byte spaces.
Output
Output the value of \(x^{a_1} + x^{a_2} + \dots + x^{a_N}\) modulo \(1,000,003\).
Sample
Sample 1
Input
2 3 1 2 3
Output
14
This represents \(x + x^2 + x^3 , x=2\). Its value is therefore as follows.
\(x + x^2 + x^3 = 2 + 4 + 8 = 14\)
Sample 2
Input
2 2 0 100
Output
253110
\(x^0 + x^{100} = 1 + 1267650600228229401496703205376 = 1267650600228229401496703205377\)
and this value modulo \(1,000,003\) is \(253110\).
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。