Profesor matematike je postavio Dragančetu sledeći zadatak. Naosnovu datog niza brojeva a₁, a₂, ..., a_n, Draganče treba daza svaku trojku indeksa (i, j, k), gde je 1 ≤ i < j < k≤ n, napiše na tabli najveći od brojeva a_i, a_j i**a_k. Zatim treba da izračuna ostatak koji daje zbir svihbrojeva koji su napisani na tabli pri deljenju sa 10007.Profesor je obećao Dragančetu peticu za kraj školske godine,ako dobije tačno rešenje pre kraja časa. Pomozite Dragančetuda što brže dobije tačan rezultat.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalazi se broj n(3 ≤ n ≤ 30000). U sledećih n redova senalaze celi brojevi a₁, a₂, ..., a_n, pri čemu je -100000≤ a_i ≤ 100000.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu izlazne datotekeispisati sumu brojeva napisanih na tabli po modulu 10007.

Primer 1:

4
3
-1
2
2

11

Objašnjenje.

Sve trojke niza brojeva su: (3, -1, 2), (3, -1, 2), (3, 2, 2), (-1, 2, 2). Na tablisu napisani brojevi 3, 3, 3, 2, pa je rešenje u ovom slučaju 11.

Primer 2:

6
8
-10
4
5
2
6

135