问题文

在一个小镇上，住着一只喜欢数列的黑猫和一只喜欢计算的狼。今天，他们决定根据一个数列进行计算并玩耍。

黑猫有一个长度为 $N$ 的整数序列 {$a_i$}，他要构造一个在相邻项之间插入 $+$ 或 $\\times$ 运算符的表达式，而狼要计算出该表达式的值。为了能够尽可能长时间地玩耍，他们决定构造所有可能的表达式（共有 $2^{N-1}$ 种），并求出这些表达式的值的总和。

最后，为了检查答案是否正确，他们请求正在进行编程训练的你编写一个程序，求出这个总和除以 $1,000,000,007 (= 10^9 + 7)$ 的余数。

请你帮助他们编写这个计算程序。

注意：请注意 $\\times$ 比 $+$ 的运算优先级高。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq a_i \leq 10^9$ $(1 \leq i \leq N)$
• $a_i$ $(1 \leq i \leq N)$ 是整数。

输入

输入以以下格式给出：

$N$

$a_1$ $...$ $a_N$

输出

输出计算结果。

示例 1

3
1 2 3

输出示例 1

24

可能的表达式有 $1+2+3$、$1+2 \\times 3$、$1 \\times 2+3$ 和 $1 \\times 2 \\times 3$ 四种。计算这些表达式的值分别为 $6$、$7$、$5$ 和 $6$，所以总和为 $6+7+5+6=24$。

示例 2

2
28055 35642

输出示例 2

0

总和是 $1000000007 (= 10^9+7)$，所以输出余数 $0$。

示例 3

12
31415926 535897932 38462643 383279502 884197 169399375 105820974 944592307 81640628 620899862 803482534 21170679

输出示例 3

626713706