CSES - Lukujono

Time limit: 4.00 s
Memory limit: 128 MB

Fibonaccin lukujono $(F_n)$ on erittäin tunnettu lukujono, ja se määritellään seuraavasti:

$F_0 = 0$
$F_1 = 1$
$F_n = F_{n - 1} + F_{n - 2}$ , jos $n \geq 2$ .

Paljon vähemmälle huomiolle on jäänyt Uolevinaccin lukujono $(U_n)$ , joka määritellään seuraavasti:

$U_0 = 0$
$U_1 = 1$
$U_n = U_{\lfloor n/2\rfloor} + U_{\lfloor n/3\rfloor} + U_{\lfloor n/4\rfloor} + U_{\lfloor n/5\rfloor} + \ldots + U_{\lfloor n/n\rfloor}$ , jos $n \geq 2$ .

Merkintä $\lfloor x \rfloor$ tarkoittaa lukua $x$ pyöristettynä alaspäin kokonaisluvuksi.

Syöte

Syötteenä annetaan yksi kokonaisluku $n$ .

Tuloste

Tulosteen tulee olla luku $U_n$ .

Rajat

$1 \leq n \leq 10^5$
Voit olettaa, että $U_n$ on enintään $10^9$ .

Esimerkki

Syöte:

Tuloste:

Selitys:

$U_1 = 1$
$U_2 = U_1 = 1$
$U_3 = U_1 + U_1 = 2$
$U_5 = U_2 + U_1 + U_1 + U_1 = 4$
$U_{10} = U_5 + U_3 + U_2 + U_2 + U_1 + U_1 + U_1 + U_1 + U_1 = 13$