小蓝有一个长度为 n 的数组 B = (b₀, b₁, · · · , b_n−1)，数组 B 是由另一个长度为 n 的环形数组 A = (a₀, a₁, · · · , a_n−1) 经过一次相邻最大化操作得到的，其中 a_i与 a_i+1 相邻，a₀ 与 a_n−1 相邻。

形式化描述为：

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

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

第二行包含 n 个整数 b₀, b₁, · · · , b_n−1，相邻两个整数之间用一个空格分隔。

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

5
8 6 1 8 8

7

对于 30% 的评测用例，3 ≤ n ≤ 10；

对于 60% 的评测用例，3 ≤ n ≤ 100；

对于所有评测用例，3 ≤ n ≤ 1000 ，0 ≤ b_i ≤ 10。