No.1084 Product of Products
タグ : / 解いたユーザー数 188
作問者 :
kichi2004_
Problem Statement
There is a sequence $A$ of non-negative integers with $N$ elements. The $i(1 \le i \le N)$-th element of $A$ is $A_i$.
Define the function $f(l,r)(1 \le l \le r \le N)$ as follows.
- $f(l,r)=A_l \times A_{l+1} \times \dots \times A_r$
Chawanmushi-kun always makes a calculation error whenever the answer is $10^9$ or greater.
Chawanmushi ANOTHER-kun never makes any calculation errors.
Chawanmushi-kun calculated $f(l,r)$ for all $N(N+1)/2$ pairs $(l,r)(1 \le l \le r \le N)$ and wrote the results down in a notepad.
Chawanmushi ANOTHER-kun erased, from the $N(N+1)/2$ numbers obtained by Chawanmushi-kun, the numbers whose calculation results are wrong.
Then, Chawanmushi ANOTHER-kun multiplied all the remaining numbers together and offered the answer to the Chawanmushi God.
Find the number that Chawanmushi ANOTHER-kun offered.
However, since the answer can be very large, output the remainder when the answer is divided by $10^9+7$.
Edit at 21:48: Unified the wording "digit" → "number" in the problem statement
Constraints
- $N,A_i$ are integers
- $1 \le N \le 10^5$
- $0 \le A_i < 10^9$
Input
$N$
$A_1\ A_2\ \dots\ A_n$
The $1$st line contains $N$.
The $2$nd line contains $A$, separated by spaces.
Output
Output the answer as an integer.
Print a newline at the end.
Sample
Sample 1
Input
3
2 3 5
Output
81000
Chawanmushi-kun wrote $(2,3,5,6,15,30)$ in the notepad. Chawanmushi ANOTHER-kun computed $81000$, the product of all of these.
Sample 2
Input
3
100000 100000 100000
Output
993000007
Chawanmushi-kun wanted to write $(10^5,10^5,10^5,10^{10},10^{10},10^{15})$ in the notepad, but made calculation errors on the $(10^{10},10^{10},10^{15})$ part.
Chawanmushi ANOTHER-kun erases that part, so he calculated $10^5 \times 10^5 \times 10^5$.
Output the remainder when the answer is divided by $10^9+7$.
Sample 3
Input
10
1 2 3 4 5 6 7 8 9 10
Output
29831907
Output the remainder when the answer is divided by $10^9+7$.
Sample 4
Input
5
31415 92653 1333 58979 32384
Output
282377886
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。