Problem 3195: Crocks

Task

You are given an array $a$ of $N$ elements.
The cost of a continuous subarray $[st, dr]$ is defined as $C(st, dr) = a_{st} \cdot (a_{st+1} + a_{st+2} + \dots + a_{dr-1}) \cdot a_{dr}$ .

You need to calculate $\sum_{st=1}^{n-2} \sum_{dr=st+2}^n C(st, dr)$ modulo $10^9+7$ .

Input data

The first line contains $N$ and the second line contains $N$ values representing the array $a$ .

Output data

A single number, the required sum modulo $10^9+7$ .

Constraints and clarifications

$1 \leq N \leq 10^6$
$1 \leq a_{i} \leq 10^9$
For $20$ points, $1 \leq N \leq 150$ .
For an additional $30$ points, $1 \leq N \leq 5\ 000$ .

Example 1

stdin

4
2 1 3 2

stdout

Explanation

$C(1, 3) = 6$

$C(1, 4) = 16$

$C(2, 4) = 6$

Example 2