P8810 [Lanqiao Cup 2022 National C] Number of Arrays

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

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 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$).

**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