题目描述

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

考虑在此序列的相邻 $2$ 项之间放置 + 或 - 以创建一个表达式。

有 $2^{N-1}$ 创建表达式的方法，但我们会将满足以下条件的表达式称为好表达式。

• - 连续出现不超过 $2$ 次。

求所有良好表达式值的总和。

可以证明，这个值始终是一个非负整数。因此，输出此值对 $10^9+7$ 取模的结果。

输入格式

输入由以下格式给出：

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