Farmer John cría vacas. Las técnicas modernas usan toros premiados muertos hace mucho, así que no necesita toros. Controla el número de terneros con la comida; da la misma cantidad a todas y producen igual número. Parte de una vaca y desea $N$ tras varias generaciones.

Si $N = 12$, alimenta la original para producir tres terneros. Cuando crecen para reproducirse, alimenta cada uno para cuatro, obteniendo doce al final. Vende cada vaca al producir crías y conserva solo la generación más reciente.

Cada generación, cada vaca tiene al menos dos terneros y sin máximo, gracias a una raza muy fuerte.

Para el entero $N$ ($1 \le N \le 2{,}000{,}000{,}000$), ¿cuántas formas distintas permiten obtener $N$ vacas desde una? La cantidad de formas de obtener $N$ no supera $2{,}000{,}000{,}000$.

Entrada

• Línea 1: entero $N$.

Salida

• Línea 1: número de formas de obtener $N$ vacas.

Ejemplos

Entrada 1

12

Salida 1

8

Nota

Detalles de la salida

Una forma de obtener doce es $(2,2,3)$: dos terneros por vaca en la primera generación, dos en la segunda y tres en la tercera, total doce jóvenes. Las otras siete son $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$.

Autor: Mihai Stroe, 2002