分数: 400 点
问题陈述
给你一系列 N 非负整数: A_1,A_2,\cdots,A_N.
考虑插入 + or - 在每对相邻项之间创建一个公式。
有 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).