P17284 "IXOI R2" Cannot Think of One

As you can see, the problem setter cannot think of a problem name again.  [Big Head].jpg

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: $$\prod_{i=1}^n x_i^{p'_i}$$ 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$.

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

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

**This problem uses bundled testdata.** | Subtask | $n\le$ | Special Property | Score | | :-----: | :----: | :--------------: | :--: | | $1$ | $8$ | None | $5$ | | $2$ | $500$ | None | $40$ | | $3$ | $8000$ | $x_i=1$ | $10$ | | $4$ | $8000$ | $x_i\in \{0,1\}$ | $20$ | | $5$ | $8000$ | None | $25$ | For all data, it is guaranteed that: It is guaranteed that $0\le x_i< 10^9+7$. Translated by ChatGPT 5