Problem Description

题目背景

月光渐淡，漫野银辉化作露；

黎明终至，冲天赤色破开云。

题目描述

lhb 喜欢观测星空。有一天 zxh 想要用 lhb 的望远镜观测星空，lhb 掏出了他的数学作业，让 zxh 解出来才能用。

求：

$$\sum_{k=1}^{n} \left\{ a_k + \sum_{i=1}^{k-1}\sum_{j=1}^{k-1} \Biggl[ \Biggl( \prod_{l=1}^{i} a_{l}^{\,2^{\,i-l}} \Biggr) \Biggl( \prod_{l=1}^{j} a_{l}^{\,2^{\,j-l}} \Biggr) \Biggr] \right\}$$

对 $10^9+7$ 取模后的结果。

输入格式

输入共 $2$ 行，第一行输入一个整数 $n$。

第二行输入 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

输出一个数表示答案。

样例

样例 1

提示

对于 $100\%$ 的数据满足 $n\le 5\times 10^6$，$a_i\le 10^9$。

子任务编号	$n\le$	特殊性质	分数
$0$	$5\times 10^6$	最难做	70
$1$	$100$	无	10
$2$	$10^3$		20

本题输入量较大，请使用较快的读入方式。

4
1 2 3 4 

245