Laboratorul de informatică al Școlii Liniare are un singur rând de $N$ calculatoare numerotate de la 1 la $N$. Fiecare dintre acestea are un buton „PWR” care dacă este apăsat va porni calculatorul (dacă acesta era oprit) sau îl va opri (dacă acesta era pornit).
Datorită poziționării geamului pe fiecare calculator s-a acumulat de-a lungul timpului o cantitate diferită de praf: primul are $N$ unități de praf, al doilea $N-1$, al treilea $N-2$ etc. Ultimul are o singură unitate.
Înainte să vină personalul de curățenie, profesorul a oprit toate calculatoarele dar a uitat să închidă ușa laboratorului. Așadar, în laborator au mai intrat $N$ elevi. Primul a apăsat butonul „PWR” pe fiecare calculator, al doilea l-a apăsat pe fiecare al doilea, al treilea pe fiecare al treilea etc. Ultimul elev a apăsat doar butonul de pe ultimul calculator.
Pentru evitarea accidentelor, personalul de curățenie va șterge praful numai de pe calculatoarele oprite, pe cele pornite va rămâne o cantitate totală de $C$ unități de praf.

Cerință

Determinați ultimele patru cifre ale lui $C$.

Date de intrare

Pe prima linie a fișierului de intrare calculatoare.in se află un singur număr natural $N$, cu semnificația din enunț.

Date de ieșire

Pe prima linie a fișierului de ieșire calculatoare.out scrieți un singur număr natural, cel format din ultimele patru cifre ale cantității totale de praf $C$.

Restricții și precizări

• $1 \leq N \leq 2 \cdot 10^9$
• Pentru 60% din teste, $1 \leq N \leq 10^6$
• Dacă $C < 1000$ va trebui afișată chiar valoarea acestuia (fără zerouri la început)

Exemplul 1

calculatoare.in

1

calculatoare.out

1

Exemplul 2

calculatoare.in

10

calculatoare.out

19

Explicație

Starea calculatoarelor la sfârșitul zilei:

nr:    1 2 3 4 5 6 7 8 9 10
praf: 10 0 0 7 0 0 0 0 2  0