题目描述

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

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

一共有 $2^{N-1}$ 种构造表达式的方法。在这些表达式中，满足以下条件的表达式被称为好表达式：

• - 不能连续出现 $2$ 次或以上。

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

输入格式

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

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

输出格式

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

样例 1

输入

3
3 1 5

输出

15

样例 2

输入

4
1 1 1 1

输出

10

样例 3

输入

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

输出

279919144

说明/提示

限制

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

样例解释 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$ 取模的结果。

由 ChatGPT 4.1 翻译