87. 数组个数
内存限制：256 MB
时间限制：1.000 S
题目描述
小蓝有一个长度为 n 的数组 B = (b0, b1, ..., bn−1)，数组 B 是由另一个长度为 n 的环形数组 A = (a0, a1, ..., an−1) 经过一次相邻最大化操作得到的，其中 ai 与 ai+1 相邻，a0 与 an−1 相邻。 形式化描述为：
输入
输入的第一行包含一个整数 n，表示数组长度。
第二行包含 n 个整数 b0, b1, ...,bn−1，相邻两个整数之间用一个空格分隔。
输出
输出一行包含一个整数表示答案，答案可能很大，请输出答案除以 1000000007（即 109 + 7）后的余数。
样例输入 复制
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 ≤ n ≤ 10；
对于 60% 的评测用例，3 ≤ n ≤ 100；
对于所有评测用例，3 ≤ n ≤ 1000，0 ≤ bi ≤ 10。