Problem Description

Xiao Lan has an array $B = (b_0,b_1,\cdots,b_{n-1})$ of length $n$. Array $B$ is obtained from another circular array $A = (a_0,a_1,\cdots,a_{n-1})$ of length $n$ by performing one adjacent maximization operation. Here $a_i$ and $a_{i+1}$ are adjacent, and $a_0$ and $a_{n-1}$ are also adjacent.

Formally:

$$b_i= \begin{cases} \max\{a_{n-1},a_0,a_1\}& i=0\\ \max\{a_{i-1},a_i,a_{i+1}\}& 0<i<n-1\\ \max\{a_{n-2},a_{n-1},a_0\}& i=n-1\\ \end{cases}$$

Xiao Lan wants to know how many arrays $A$ can satisfy the condition such that after one adjacent maximization operation, array $B$ can be obtained. Note that every element in $A$ must be a non-negative integer.

Input Format

The first line contains an integer $n$, indicating the length of the array.

The second line contains $n$ integers $b_0,b_1,\cdots,b_{n-1}$, with a single space between adjacent integers.

Output Format

Output one line containing an integer representing the answer. The answer may be very large, so output the remainder after dividing by $1000000007$ (i.e. $10^9+7$).

5
8 6 1 8 8

7

Hint

Sample Explanation

There are $7$ possible arrays $A$: $(6,0,0,1,8)$, $(6,0,1,0,8)$, $(6,0,1,1,8)$, $(6,1,0,0,8)$, $(6,1,0,1,8)$, $(6,1,1,0,8)$, $(6,1,1,1,8)$.

Constraints

For $30\%$ of the testdata, $3 \le n \le 10$.

For $60\%$ of the testdata, $3 \le n \le 100$.

For all testdata, $3 \le n \le 1000$, $0 \le b_i \le 10$.

Lanqiao Cup 2022 National Contest, Group C, Problem G.

Translated by ChatGPT 5