Sum of Maximum Non‐Adjacent Subsequence Sums

You are given a non-negative integer sequence \( a_1, a_2, \dots, a_n \) of length \( n \). For any interval \([l,r]\) (with \(1 \le l \le r \le n\)), define \( f(l, r) \) as the maximum sum obtainable by selecting a subset of elements from \( a_l, a_{l+1}, \dots, a_r \) such that no two chosen elements are adjacent.

Your task is to compute

\[ S = \left[ \sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \right] \bmod (10^9+7), \]

and output the value of \(S\).

Note: Since \(a_i\) are non-negative, the decision is to pick an element or not subject to the constraint of non-adjacency. The well-known recurrence is:

\[ \begin{aligned} \mathit{dp}[i] &= \max(\mathit{dp}[i-1], \mathit{dp}[i-2] + a_i), \quad i \ge 2, \\ \mathit{dp}[1] &= a_1, \\ \mathit{dp}[0] &= 0. \end{aligned} \]

You need to sum \(f(l, r)\) for all valid intervals \([l, r]\).

inputFormat

The first line contains a single integer \( n \) (the length of the sequence).

The second line contains \( n \) space-separated non-negative integers \( a_1, a_2, \dots, a_n \).

outputFormat

Output a single integer: the value of \( S \) modulo \(10^9+7\).

sample

1
5

5

</p>