凛冬将至

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

一支军队有 $n$ 名士兵，第 $i$ 名士兵的力量为 $a_i$。

选取下标严格递增的非空序列 $i_1,i_2,\ldots,i_k$。如果

则称这组士兵为一个氏族，其力量为

军队的力量定义为所有可能氏族的力量之和。请输出军队力量对 $10^9+7$ 取模的结果。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示军队的力量对 $10^9+7$ 取模的结果。

样例输入

2
3 3

样例输出

12

样例说明

三个氏族分别为两个单元素氏族和包含两名士兵的氏族，其力量之和为 $3+3+2\times3=12$。

数据范围

$1\le n\le 200000$，$1\le a_i\le 1000000$。