Background

As you can see, the problem setter cannot think of a problem name again.

[Big Head].jpg

Problem Description

Given a sequence $x$ of length $n$.

You have a sequence $p$ of length $n$, initially $\forall i\in [1,n],p_i=1$.

Define one operation as: choose $i\in[1,n]$, and move the numbers at positions $i-1$ and $i+1$ in the sequence to position $i$.

Formally, each operation can be seen as setting:

• $p_i\leftarrow p_i+p_{i-1}+p_{i+1}$;
• $p_{i-1}\leftarrow 0$;
• $p_{i+1}\leftarrow 0$.

In particular, if position $i-1$ or $i+1$ does not exist, then no operation is performed at position $i-1$ or $i+1$.

We call a sequence $p'$ stupid if and only if it can be generated from the initial sequence $p$ by performing the operation any number of times.

We call two sequences $a,b$ essentially different if and only if $\exist i\in [1,n],a_i\neq b_i$.

Define the weight of a sequence $p'$ as:

Now, compute the sum of weights of all essentially different stupid sequences $p'$, and output the result modulo $10^9+7$.

Here, it is considered that $0^0=1$.

Input Format

The input has two lines. The first line contains an integer $n$. The second line contains an array $x$ of length $n$.

Output Format

Output one integer, representing the sum of weights of all essentially different stupid sequences $p'$, modulo $10^9+7$.

6
2 3 1 5 6 6

648718

5
17 43 2 6 7

207004448

Hint

This problem uses bundled testdata.

For all data, it is guaranteed that:

It is guaranteed that $0\le x_i< 10^9+7$.

Translated by ChatGPT 5