AT_bcu30_f 数列と計算

在某个小镇上，住着一只喜欢数列的黑猫和一只喜欢计算的狼。今天，他们决定一起用某个数列进行计算游戏。 黑猫拥有一个长度为 $N$ 的整数序列 $\{a_i\}$，他会在这个数列相邻的项之间插入 $+$ 或 $×$，组成一个表达式。然后，狼会计算这些表达式的值。两人想用这个整数序列尽可能长时间地玩下去，于是他们决定，把所有可以组成的表达式（总共有 $2^{N-1}$ 种）都列出来，并计算所有表达式值的总和。 为了最终检查答案是否正确，他们想把这个总和对 $1,000,000,007\ (=\ 10^9+7)$ 取模。于是，两人请求你——在编程竞赛中不断磨练自己的你——编写程序帮他们完成这个计算。 需要注意的是，$×$ 的运算优先级高于 $+$。

输入按以下形式给出： > $N$ $a_1$ $a_2$ … $a_N$

输出所求的答案。

### 约束条件 - $1\leq N\leq 10^5$ - $1\leq a_i\leq 10^9$ $(1\leq i\leq N)$ - $a_i$ 是整数。 ### 样例解释 1 所有可能的表达式为，$1+2+3$，$1+2×3$，$1×2+3$，$1×2×3$ 共 $4$ 种。计算这些式子，答案分别为 $6$、$7$、$5$、$6$，所以总和为 $6+7+5+6=24$。 ### 样例解释 2 所求总和为 $1000000007\ (=10^9+7)$，因此对 $10^9+7$ 取模后输出 $0$。 由 ChatGPT 5 翻译