题目描述

给定一个长度为$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

3
3 1 5

示例输出 1

15

我们有以下三个好的表达式：

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

注意到$3-1-5$不是好的表达式，因为其中连续出现了两个-符号。因此，答案是$9+(-1)+7=15$。

示例输入 2

4
1 1 1 1

示例输出 2

10

我们有以下五个好的表达式：

• $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
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

示例输出 3

279919144

打印求和结果对$(10^9+7)$取模的值。