Description

YSGH has a non-negative integer sequence $a$ of length $n$. Define $f(l, r)$ as the maximum possible sum of some pairwise non-adjacent numbers chosen from the subarray $[l, r]$ of sequence $a$.

YSGH wants to know $\displaystyle \left[ \sum_{l = 1}^{n} \sum_{r = l}^{n} f(l, r) \right] \bmod ({10}^9 + 7)$.

Input Format

The first line contains a positive integer $n$, denoting the length of the sequence.

The second line contains $n$ non-negative integers $a_1, a_2, \ldots , a_n$.

Output Format

Only one line containing one integer, denoting the answer.

3
1 2 4

18

Hint

Sample Explanation

$f(1, 1)=1$, $f(1, 2)=2$, $f(1, 3)=5$, $f(2, 2)=2$, $f(2, 3)=4$, $f(3, 3)=4$.

The answer is $1 + 2 + 5 + 2 + 4 + 4 = 18$.

Constraints

For $100\%$ of the testdata, $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 \}$, where $x$ is an integer greater than $1$.
• Subtask 5 (30 points): No special constraints.

Translated by ChatGPT 5