配点 : 100 点
問題文
在某个城镇里,住着一只非常喜欢数列的黑猫和一只非常喜欢计算的狼。今天,他们决定根据一个数列一起进行计算游戏。
黑猫有一个长度为 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 可以得到第 4 类型。 计算这些公式后,答案是 6、7、5、6 ,所以总数是 6+7+5+6=24 。
入力例 2
2 28055 35642
出力例 2
0
所需总数为 1000000007 (= 10^9+7) ,所以用它作为 余数除以 10^9+7 余数除以 0 。
入力例 3
12 31415926 535897932 38462643 383279502 884197 169399375 105820974 944592307 81640628 620899862 803482534 21170679
出力例 3
626713706