No.1084 積の積

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 184
作問者 :

tyawanmusi / テスター :

kichi2004_

22 ProblemId : 3681 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-06-19 21:48:01

問題文

要素数 $N$ の非負整数列 $A$ があります。 $A$ の $i (1 \leq i \leq N)$ 番目の要素は $A_{i}$ です。
関数 $f (l, r) (1 \leq l \leq r \leq N)$ を次のように定義します。

$f (l, r) = A_{l} \times A_{l + 1} \times \dots \times A_{r}$

掛け算がマイブームの茶碗蒸しくんと、掛け算をキメたい茶碗蒸しANOTHERくんがいます。
茶碗蒸しくんは、答えが $10^{9}$ 以上になると必ず計算ミスをしてしまいます。
茶碗蒸しANOTHERくんは一切計算ミスをしません。

茶碗蒸しくんは

N (N + 1) / 2

通りある

(l, r) (1 \leq l \leq r \leq N)

すべてについて

f (l, r)

を計算し、メモ帳に書き残しました。
茶碗蒸しANOTHERくんは、茶碗蒸しくんが求めた

N (N + 1) / 2

個の数から計算結果が間違っている数を消しました。
そして、茶碗蒸しANOTHERくんは残った数を全て掛け合わせ、その答えを茶碗蒸し神に奉納しました。
茶碗蒸しANOTHERくんが奉納した数を求めてください。
ただし、答えはとても大きな数になることがあるので、答えを

10^{9} + 7

で割ったあまりを出力してください。

21:48編集：問題文中の「数字」→「数」に統一

制約

$N, A_{i}$ は整数
$1 \leq N \leq 10^{5}$
$0 \leq A_{i} < 10^{9}$

入力

 $N$ 
 $A_{1} A_{2} \dots A_{n}$

$1$ 行目には $N$ が入力されます。
$2$ 行目には $A$ が空白区切りで入力されます。

出力

答えを整数で出力してください。
最後に改行してください。

サンプル

サンプル1

入力

3
2 3 5

出力

茶碗蒸しくんは、 $(2, 3, 5, 6, 15, 30)$ をメモ帳に書きました。茶碗蒸しANOTHERくんは、これらの総乗である $81000$ を求めました。

サンプル2

入力

3
100000 100000 100000

出力

993000007

茶碗蒸しくんは $(10^{5}, 10^{5}, 10^{5}, 10^{10}, 10^{10}, 10^{15})$ をメモ帳に書きたかったですが、 $(10^{10}, 10^{10}, 10^{15})$ の部分で計算ミスをしてしまいました。
茶碗蒸しANOTHERくんはその部分を消すので、 $10^{5} \times 10^{5} \times 10^{5}$ を計算しました。
答えを $10^{9} + 7$ で割ったあまりを出力してください。

サンプル3

入力

10
1 2 3 4 5 6 7 8 9 10

出力

29831907

答えを $10^{9} + 7$ で割ったあまりを出力してください。

サンプル4

入力

5
31415 92653 1333 58979 32384

出力

282377886

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。