不条理狂诗曲

YSGHYYDS

YSGH 有一个长度为 $n$ 的非负整数序列 $a$，定义 $f(l, r)$ 表示从 $a$ 序列的区间 $[l, r]$ 选择若干不相邻的数的和的最大值。 YSGH 想知道 $\displaystyle \left[ \sum_{l = 1}^{n} \sum_{r = l}^{n} f(l, r) \right] \bmod ({10}^9 + 7)$ 。

第一行，一个正整数 $n$，表示序列长度。 第二行，$n$ 个非负整数 $a_1, a_2, \ldots , a_n$。

仅一行，一个整数，表示答案。

3
1 2 4

18

**【样例解释】** $f(1, 1)=1$，$f(1, 2)=2$，$f(1, 3)=5$，$f(2, 2)=2$，$f(2, 3)=4$，$f(3, 3)=4$。 答案为 $1 + 2 + 5 + 2 + 4 + 4 = 18$。 --- **【数据范围】** 对于 $100 \%$ 的数据，$1 \le n \le {10}^5$，$0 \le a_i \le {10}^9$。 - Subtask 1（10 points）：$n \le 500$。 - Subtask 2（20 points）：$n \le 5000$。 - Subtask 3（20 points）：$a_i \in \{ 0, 1 \}$。 - Subtask 4（20 points）：$a_i \in \{ 1, x \}$，$x$ 是大于 $1$ 的整数。 - Subtask 5（30 points）：无特殊限制。