游游的回文子串

题号：NC258934
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

游游拿到了一个01串，该字符串仅由'0'和'1'两种字符组成，且第一个字符保证是'1'。
由于该字符串过长，游游用一个大小为 $n$ 的数组表示该字符串：
第一个元素 $a_1$ 表示字符串开头有 $a_1$ 个'1'字符，第二个元素 $a_2$ 表示紧接着有 $a_2$ 个'0'字符，三个元素 $a_3$ 表示紧接着有 $a_3$ 个'1'字符，以此类推。这样就表示了一个长度为 $\sum_{i=1}^na_i$ 的01串。

游游想知道，该01串共有多少个非空回文子串？由于答案可能过大，请对 $10^9+7$ 取模。

回文的定义：字符串正着读和倒着读相同，例如"101101"是回文串。
子串的定义：字符串取一段连续的部分，例如"011"是"1011"的子串。

输入描述:

第一行输入一个正整数，代表数组的大小。
第二行输入个正整数，代表数组的元素。

输出描述:

回文子串的数量，答案对取模。

示例1

输入

复制

1
3

输出

复制

说明

该数组表示的字符串是"111"，共有6个子串，所有子串都是回文的，所以答案是6。

示例2

输入

复制

3
1 1 1

输出

复制

说明

该数组表示的字符串是"101"，长度为1的三个子串都是回文的，长度为2的两个子串都不回文，长度为3的一个子串回文。答案是3+1=4。