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

形式化描述為： 

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

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

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

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

5
8 6 1 8 8

7

可能的 A 數(shù)組有 7 個(gè)：(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) 。

對(duì)于 30% 的評(píng)測(cè)用例，3 ≤ n ≤ 10；

對(duì)于 60% 的評(píng)測(cè)用例，3 ≤ n ≤ 100；

對(duì)于所有評(píng)測(cè)用例，3 ≤ n ≤ 1000 ，0 ≤ b_i ≤ 10。