Reconstructing the Original Circular Array

There is a circular array \(A = (a_0, a_1, \dots, a_{n-1})\) of non‐negative integers. From it one obtains another array \(B = (b_0, b_1, \dots, b_{n-1})\) by performing an adjacent maximization operation exactly once. In other words, for every index \(i\) (with indices taken modulo \(n\)) the following holds:

[ 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} ]

Given the array \(B\) (of length \(n\)), count how many arrays \(A\) (with non‐negative integers) could produce \(B\) by the operation described above. Since the answer can be large, output it modulo \(10^9+7\;\).

Note: It is guaranteed that \(B\) is obtained from some array \(A\) using the above operation. For this problem, you may assume that \(n\) as well as the entries of \(B\) are small. In particular, you may assume \(1 \le n \le 10\) and \(0 \le b_i \le 10\) for all \(i\).

Explanation: For every index \(i\), the condition

[ \max{a_{i-1},a_i,a_{i+1}} = b_i ]

forces that in the three consecutive entries (taking indices modulo \(n\)) at least one must equal \(b_i\) and all three should be at most \(b_i\) (when considering the constraint given by the corresponding position in \(B\)). Also, each element \(a_j\) appears in three such triplets, namely those centered at \(j-1, j, j+1\) (modulo \(n\)), so its maximum allowed value is \(\min(b_{j-1}, b_j, b_{j+1})\). A careful counting (for small \(n\)) is needed to satisfy all these overlapping conditions.

inputFormat

The first line contains a single integer \(n\) (\(1\le n\le 10\)). The second line contains \(n\) space‐separated integers \(b_0, b_1, \dots, b_{n-1}\) (\(0 \le b_i \le 10\)).

outputFormat

Output a single integer, the number of arrays \(A\) that produce \(B\) via the adjacent maximization operation, modulo \(10^9+7\;\).

sample

1
5

1