Array Modification

You are given an array A of N integers. For every index i of the array A, you need to select an index jsuch that ji and the product of A[i] and A[j] is maximum for that i . Finally, you need to print the sum of A[i]A[j] for all the indices i . Since this sum can be large, you need to print it to the modulo 10^9+7.

Note: Please refer to the sample explanation section.

Input format

First line: Integer N denoting the number of elements in the array A

Next line: N space-separated integers denoting the elements of the array A

Output format

Print the required sum to the modulo 10^9+7.

Constraints

2N10^5

10^18A[i]10^18

SAMPLE INPUT

4 1 -9 2 -1 

SAMPLE OUTPUT

22 

Explanation

For anelement with the index 1, you can choose another index as 3, so its maximum product will be12=2

For an element with the index 2, you can choose another index as 4, so its maximum product will be91=9

For an element with the index 3, you can choose another index as 1, so its maximum product will be21=2

For an element with the index 4, you can choose another index as 2, so its maximum product will be19=9

Hence, the final answer will be2+9+2+9=22.

.