Farmer John alleva mucche. Le tecniche moderne usano tori premiati morti da tempo, quindi non servono tori. La quantità di cibo controlla i vitelli; tutte ricevono uguale cibo e ne producono ugual numero. Parte da una mucca e vuole $N$ dopo alcune generazioni.

Se $N = 12$, nutre la prima per tre vitelli. Quando la nuova generazione è abbastanza adulta, nutre ciascuna per quattro, ottenendo dodici alla fine. Ogni madre viene venduta dopo i piccoli; rimane solo l’ultima generazione.

Ogni generazione ciascuna mucca produce almeno due vitelli, senza limite massimo, grazie a una razza molto forte.

Per l’intero $N$ ($1 \le N \le 2{,}000{,}000{,}000$), quanti modi diversi consentono di ottenere $N$ mucche partendo da una? Il numero di modi per ottenere $N$ non supera $2{,}000{,}000{,}000$.

Input

• Riga 1: intero $N$.

Output

• Riga 1: numero di modi di ottenere $N$ mucche.

Esempi

Input 1

12

Output 1

8

Spiegazione

Dettagli dell’output

Un modo per dodici è $(2,2,3)$: due vitelli per mucca nella prima generazione, due nella seconda, tre nella terza, dodici giovani in totale. Gli altri sette sono $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$.

Autore: Mihai Stroe, 2002