小藍(lán)有一個長度為 n 的數(shù)組 B = (b₀, b₁, · · · , b_n?1)，數(shù)組 B 是由另一個長度為 n 的環(huán)形數(shù)組 A = (a₀, a₁, · · · , a_n?1) 經(jīng)過一次相鄰最大化操作得到的，其中 a_i與 a_i+1 相鄰，a₀ 與 a_n?1 相鄰。

形式化描述為：

小藍(lán)想知道，可能有多少個滿足條件的數(shù)組A，經(jīng)過一次相鄰最大化操作后能得到數(shù)組 B，注意 A 中的每個元素都要求為非負(fù)整數(shù)。

輸入的第一行包含一個整數(shù) n ，表示數(shù)組長度。

第二行包含 n 個整數(shù) b₀, b₁, · · · , b_n?1，相鄰兩個整數(shù)之間用一個空格分隔。

輸出一行包含一個整數(shù)表示答案，答案可能很大，請輸出答案除以 1000000007 后的余數(shù)。

5
8 6 1 8 8

7

對于 30% 的評測用例，3 ≤ n ≤ 10；

對于 60% 的評測用例，3 ≤ n ≤ 100；

對于所有評測用例，3 ≤ n ≤ 1000 ，0 ≤ b_i ≤ 10。