题目内容

在古老而神秘的岛国里，流传着一个神秘的传说：如果能够解开岛国里的谜题，就可以得到无尽的财富和荣耀。作为一个勇敢的冒险家，小红听说了这个传说，他深深地被吸引，决定前往这个岛国一探究竟。

在岛国中，小红获得了一个秘密任务：他需要解开一个神秘的数字谜题。他来到了一个神秘的洞穴，里面有一些奇怪的符号和数字。他看到了一个特别的 $01$ 串，由于太长了，他无法记住整个 $01$ 串。

于是他记录下了每一段连续的数字中 0 和 1 的数量，即用一个大小为 $n$ 的数组来表示该数字串，其中第一个元素 $a_1$ 表示数字串开头有 $a_1$ 个 1，第二个元素 $a_2$ 表示紧接着有 $a_2$ 个 0，第三个元素 $a_3$ 表示紧接着有 $a_3$ 个 1，以此类推。这样就表示了一个长度为 $\sum^n _{i=1} a_i$ 的数字串。

然而，这还不是全部的挑战。他需要进一步计算该 $01$ 串中非空回文子串的数量（由于答案可能过大，请对 $10^9+7$ 取模），才能得到该谜题的答案，但是挑战仅凭他一个人无法解决，所以他需要你的帮助，你能帮帮他吗？

回文的定义：字符串正着读和倒着读相同，例如 101101 是回文串。

子串的定义：字符串取一段连续的部分，例如 011 是 1011 的子串。

输入描述

第一行输入一个正整致 $n$ ，代表数组的大小。

第二行输入 $n$ 个正整数 $a_i$ ，代表数组的元素。

$1\le n\le 1000$ ， $1 \le a_i \le 10^9$

输出描述

回文子串的数量，答案对 $10^9+ 7$ 取模。

样例

样例1

输入

2
2 1

输出

4

样例2

输入

4
1 2 2 1

输出

10