← 返回题目列表

AtCoder · arc122_a

A. 许多公式

中文机器翻译题面 查看原题

分数: 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).