题目描述

青有一个长度为 $N$ 的非负整数序列 $A_1,A_2,\cdots,A_N$。

他考虑在这个数列的相邻两个数之间插入 + 或 -，从而构造出一个表达式。

一共有 $2^{N-1}$ 种构造表达式的方法。在这些表达式中，青喜欢所有满足 - 不连续出现（即 - 不相邻）的表达式。

请你求出青喜欢的表达式的值之和。可以证明，这个值一定是非负整数。请输出这个值对 $10^9+7$ 取模的结果。

限制条件

• $1\leq N\leq 10^5$
• $1\leq A_i\leq 10^9$
• 输入的所有值均为整数

输入格式

输入以如下格式从标准输入读入：

$N \\$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出答案对 $10^9+7$ 取模的结果。

输入输出样例 #1

输入 #1

3
3 1 5

输出 #1

15

输入输出样例 #2

输入 #2

4
1 1 1 1

输出 #2

10

输入输出样例 #3

输入 #3

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

输出 #3

279919144

样例解释 1

可以构造出以下 $3$ 种青喜欢的表达式：

• $3+1+5=9$
• $3+1-5=-1$
• $3-1+5=7$

注意 $3-1-5$ 由于 - 连续出现了 $2$ 次，因此不是青喜欢的表达式。

所以答案为 $9+(-1)+7=15$。

样例解释 2

可以构造出以下 $5$ 种青喜欢的表达式：

• $1+1+1+1=4$
• $1+1+1-1=2$
• $1+1-1+1=2$
• $1-1+1+1=2$
• $1-1+1-1=0$

所以答案为 $4+2+2+2+0=10$。

样例解释 3

请输出答案对 $10^9+7$ 取模的结果。