Norma

Ο Mirko πήρε έναν πίνακα από ακέραιους αριθμούς για τα γενέθλιά του από τη γιαγιά του Norma. Όπως κάθε άλλο παιδί, ήλπιζε για κάποια χρήματα, αλλά πήρε έναν πίνακα. Ευτυχώς, στην πόλη του υπάρχει ένα ενεχυροδανειστήριο που αγοράζει πίνακες. Το κόστος ενός πίνακα ακεραίων είναι ~min \times max \times L~ kunas, όπου ~min~ είναι ο ελάχιστος ακέραιος στον πίνακα, ~max~ είναι ο μέγιστος και ~L~ είναι το μήκος του πίνακα. Ο Mirko πρόκειται να πουλήσει μια ακολουθία διαδοχικών αριθμών από τη σειρά του.Υπολόγισε τη μέση τιμή όλων αυτών των υποακολουθιών.

Για να ελέγξει το αποτέλεσμά του, θέλει να κάνετε το ίδιο. Θα είναι ευχαριστημένος μόνο με τα τελευταία 9 ψηφία του αθροίσματος όλων των τιμών, επομένως δεν χρειάζεται να ασχολείστε με μεγάλους και πραγματικούς αριθμούς.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο αριθμό ~N (1 \leq N \leq 500\,000)~.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει ένα μέλος του πίνακα του Mirko. Τα μέλη του πίνακα θα είναι ακέραιοι από το διάστημα ~[1,\;10^8]~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει έναν ακέραιο αριθμό, τα τελευταία 9 ψηφία του απαιτούμενου αθροίσματος από την εργασία. Δεν χρειάζεται να τυπώσετε τα πρώτα μηδενικά αυτού του 9ψήφιου ακέραιου αριθμού.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας ~40~% των συνολικών πόντων, θα έχει ~N < 5\,000~.

Παραδείγματα

input

2
1
3

output

16

Επεξήγηση του 1ου παραδείγματος:

Ο πίνακας αποτελείται από δύο ακέραιους αριθμούς, το ~1~ και το ~3~. Οι πιθανές υποακολουθίες που μπορεί να πουλήσει η Mirko είναι ~(1),\;(3)~ και ~(1,\;3)~, με τις τιμές τους να είναι ~1,\;9~ και ~6~, αντίστοιχα, που είναι άθροισμα ~16~.

input

4
2
4
1
4

output

109

Επεξήγηση του 2ου παραδείγματος:

Οι πιθανές υποακολουθίες που μπορεί να πουλήσει η Mirko είναι ~(2),\;(4),\;(1),\;(4),\;(2,\;4),\;(4,\;1),\;(1,\;4),\;(2,\;4,\;1),\;(4,\;1,\;4)~ και ~(2,\;4,\;1,\;4)~. Οι τιμές τους είναι ~4,\;16,\;1,\;16,\;16,\;8,\;8,\;12,\;12~ και ~16~ αντίστοιχα, που είναι ~109~ συνολικά.

input

6
8
1
3
9
7
4

output

1042