题目描述

$n$ 个点组成的完全二叉树，第 $i$ 层节点的权值是 $a_i$。

对于所有的点对 $p,q(1 \leq p \leq q \leq n)$，请计算 $\sum val_p * val_q$。其中 $val_p$ 为 $p$ 点的权值。

根节点位于第 $1$ 层。

请输出答案对 $10^9+7$ 取模后的结果。

输入格式

输入第一行包含一个正整数$n$

输入第二行包含$100$个正整数，其中第$i$个正整数表示$a_i$。如果$n$个点组成的完全二叉树小于$i$层，则不考虑该$a_i$即可，但仍需要输入该$a_i$。

输出格式

输出一行一个整数表示答案。

3
1 2 3

17

5
1 2 3

74

数据规模与约定

样例只给出前$3$层$a_i$，在测试数据中给出前$100$层$a_i$。

对于所有的数据，$1\leq a_i\leq 10^9$。

对于 10% 的数据，$1 \leq n \leq 10$。

对于 10% 的数据，$1 \leq n \leq 10^3$。

对于 40% 的数据，$1 \leq n \leq 10^9$。

对于 40% 的数据，$1 \leq n \leq 10^{18}$。

大样例

大样例下载