Задача 21846. Differences

John Doe has an array a with n elements. John wants to find the value , that is, the sum of the squared differences of the array elements over all possible i, j pairs.

For example, for the array {1, 2, 3}, this value will be equal to (1 - 1)2 + (1 - 2)2 + (1 -  3)2 + (2 - 1)2 + (2 - 2)2 + (2 - 3)2 + (3 -  1)2 + (3 - 2)2 + (3 - 3)2 = 0 + 1 + 4 +  1 + 0 + 1 + 4 + 1 + 0 = 12

Find the remainder when S is divided by 10⁸.

Recall how to work with remainders from division. The remainder of the division of the number a by the number b will be denoted as . The following relations are true:

• 
• 
• (for a ≥ b).

For example, you want to calculate the value of . You cannot multiply these three numbers in the standard data type, but you can use the first ratio and calculate first Now you can multiply the resulting number and 107 + 3 and get .

The first line contains an integer n (1 ≤ n ≤ 10⁶) — the number of array elements. The second line contains n space-separated integers a1, ..., an (1 ≤ a_i ≤ 10⁹).

Print the remainder after dividing S by 10⁸.

Input

3
1 2 3

12

5
100 1 9 1 3

74928

2
1000000000 1

2

Tests are divided into several groups, but are evaluated separately.

• n, a_i ≤ 1000 – 10 points
• n ≤ 5000 – 10 points
• n ≤ 10⁶ a_i≤ 5000 – 30 points
• Without additional restrictions — 50 points

For example, if you solve a problem for n ≤ 5000 and arbitrary a_i you will get 20 points (first and second groups).