Sequence (Easy)

Interview

Time limit1sMemory limit512 MB

Summary

Given a sequence of positive integers, sum A_i times A_j over every pair i < j and print the result modulo 1,000,000,007.

Level: Easy3 of 10
Topics: Math, Prefix sum, Array, Combinatorics
Solved: No attempts yet

Problem

A sequence $A_1, A_2, \cdots, A_N$ of length $N$ is given, and every element is a positive integer. Find the remainder when the sum of $A_i \times A_j$ over all integer pairs $(i, j)$ with $1 \le i < j \le N$ is divided by $1\,000\,000\,007$ .

Input

The first line gives the length $N$ of the sequence $A$ .

The second line gives the sequence $A_1, A_2, \cdots, A_N$ , separated by spaces.

Output

Print the remainder when the sum of $A_i \times A_j$ over all integer pairs $(i, j)$ with $1 \le i < j \le N$ is divided by $1\,000\,000\,007$ .

Constraints

$2 \le N \le 500\,000$
$1 \le A_i \le 500\,000$ ( $1 \le i \le N$ )

Examples1

Example 1
Input
```
3
1 2 3
```
Expected output
```
11
```