题目背景

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）：无特殊限制。