問題一覧 > 通常問題

No.1084 積の積

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 135
作問者 : tyawanmusityawanmusi / テスター : kichi2004_kichi2004_
19 ProblemId : 3681 / 出題時の順位表
問題文最終更新日: 2020-06-19 21:48:01

問題文

要素数 $N$ の非負整数列 $A$ があります。 $A$ の $i(1 \le i \le N)$ 番目の要素は $A_i$ です。
関数 $f(l,r)(1 \le l \le r \le 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 \le l \le r \le N)$ すべてについて $f(l,r)$ を計算し、メモ帳に書き残しました。
茶碗蒸しANOTHERくんは、茶碗蒸しくんが求めた $N(N+1)/2$ 個の数から計算結果が間違っている数を消しました。
そして、茶碗蒸しANOTHERくんは残った数を全て掛け合わせ、その答えを茶碗蒸し神に奉納しました。
茶碗蒸しANOTHERくんが奉納した数を求めてください。
ただし、答えはとても大きな数になることがあるので、答えを $10^9+7$ で割ったあまりを出力してください。

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

制約

  • $N,A_i$は整数
  • $1 \le N \le 10^5$
  • $0 \le A_i < 10^9$

入力

$N$
$A_1\ A_2\ \dots\ A_n$

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

出力

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

サンプル

サンプル1
入力
3
2 3 5
出力
81000

茶碗蒸しくんは、 $(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もしくは右上の雲マークをクリックしてアカウントを作成してください。