У чарівному королівстві жила принцеса, яка мала скриньку з перлинами. Кожна перлина мала свій унікальний номер. Принцеса часто гралася з перлинами, складаючи їх у пари і підраховуючи деякі властивості.

Одного разу принцеса вирішила визначити спеціальну функцію для своїх перлин. Вона визначила функцію $f(x, y)$ для двох позитивних чисел $x$ і $y$ як остачу від ділення $(x + y)$ на $10^8$.

Принцеса мала послідовність позитивних чисел $A = (A_1, \ldots, A_N)$ довжиною $N$. Їй потрібно знайти значення наступного виразу:

$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} f(A_i, A_j)$

Input Specification

У першому рядку міститься ціле число $N$ --- кількість перлин у скриньці.$(2 \le N \le 3 \times 10^5)$

У другому рядку містяться $N$ цілих чисел $A_1, A_2, \ldots, A_N$ --- номери перлин. $(1 \le A_i < 10^8)$

Output Specification

Виведіть відповідь на задачу.

Sample Input 1

3
3 50000001 50000002

Sample Output 1

100000012

Sample Input 2

5
1 3 99999999 99999994 1000000

Sample Output 2

303999988