问题描述

小蓝有一个长度为 $n$ 的数组 $B=(b_0, b_1, \cdots, b_{n-1})$, 数组 $B$ 是由另一个长度 为 $n$ 的环形数组 $A=(a_0, a_1, \cdots, a_{n-1})$ 经过一次相邻最大化操作得到的, 其中 $a_i$ 与 $a_{i+1}$ 相邻, $a_0$ 与 $a_{n-1}$ 相邻。

形式化描述为:

$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}$

小蓝想知道, 可能有多少个满足条件的数组 $A$, 经过一次相邻最大化操作后能得到数组 $B$, 注意 $A$ 中的每个元素都要求为非负整数。

输入格式

输入的第一行包含一个整数 $n$, 表示数组长度。

第二行包含 $n$ 个整数 $b_0, b_1, \cdots, b_{n-1}$, 相邻两个整数之间用一个空格分隔。

输出一行包含一个整数表示答案, 答案可能很大, 请输出答案除以 1000000007 后的余数。

5
8 6 1 8 8

7

样例说明

可能的 $A$ 数组有 7 个: $(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)$。

评测用例规模与约定

对于 30% 的评测用例, $3 \leq n \leq 10$;

对于 60% 的评测用例, $3 \leq n \leq 100$；

对于所有评测用例, $3 \leq n \leq 1000,0 \leq b_i \leq 10$。