解题思路

全相同的一段内部所有子串都是回文，贡献 $a(a+1)/2$。相邻两段字符不同，偶回文无法跨段。跨至少三段的奇回文：取奇数段 $i..j$（$j-i$ 为偶数），中间段的长度序列成回文时，两端各取 $x=1..\min(a_i,a_j)$ 个字符，贡献 $\min(a_i,a_j)$。

复杂度分析

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

代码实现

题目内容

磁盘上的比特流被压成 $n$ 段交替游程：第 1 段是 $a_1$ 个 1，第 2 段是 $a_2$ 个 0，第 3 段又是 1，依此类推。完整性校验需要统计该比特流中非空回文子串的个数。答案可能很大，请对 1000000007 取模。

回文指正着读和倒着读相同；子串指连续一段。

约束：$1 \le n \le 10^3$，$1 \le a_i \le 1000000000$。

输入描述

第一行一个正整数 $n$。 第二行 $n$ 个正整数 $a_i$。

输出描述

输出回文子串个数对 1000000007 取模的结果。

样例1

输入

3
3 1 3

输出

16

说明

按题意模拟计算得到。

样例2

输入

1
5

输出

15

说明

按题意模拟计算得到。

样例3

输入

5
1 1 1 1 1

输出

9

说明

按题意模拟计算得到。