数列运算

【题目描述】

在纸上有一个长为 $n$ 的数列，第 $i$ 项值为 $a_i$。

现在小 $A$ 想要在这些数之间添加加号或乘号。问对于不同的 $2^{n−1}$ 种方案，所有答案的和是多少？

由于数据范围较大，所以输出对 $1000000007$ 取模的结果。

【输入格式】

输入第一行一个整数 $n$ 表示数列的长度。

之后一行 $n$ 个整数，第 $n$ 个整数表示数列的第 $i$ 项 $a_i$。

【输出格式】

$m$ 行，第 $i$ 行表示第 $i$ 个询问的答案对 $1000000007$ 取模的结果。

【样例1输入】

3
1 2 4

【样例1输出】

30

【样例2输入输出】

点击下载样例2

【数据范围与约定】

对于 $30\%$ 的数据，$1 ≤ n ≤ 10, 1 ≤ a_i ≤ 10^5$；

对于另外 $30\%$ 的数据，$1 ≤ n ≤ 1000, a_i = 1$；

对于 $90\%$ 的数据，$1 ≤ n ≤ 1000, 1 ≤ a_i ≤10^5$；

对于 $100\%$ 的数据，$1 ≤ 100000, 1 ≤ a_i ≤10^9$。

【来源】

清北学堂济南NOIP集训二试$T_2$