Farmer John fait reproduire ses vaches. Les techniques modernes utilisant des taureaux primés morts depuis longtemps dispensent de taureaux. La quantité de nourriture contrôle le nombre de veaux ; toutes reçoivent la même quantité, donc en produisent autant. Il part d’une vache et veut $N$ vaches après quelques générations.

Si $N = 12$, il nourrit la première pour trois veaux. Quand cette génération est assez âgée, il nourrit chacune pour quatre veaux, soit douze à la fin. Une vache est vendue dès qu’elle a des petits ; seule la génération la plus récente reste.

Chaque génération, chaque vache produit au moins deux veaux, sans limite supérieure : la race est très robuste.

Pour l’entier $N$ ($1 \le N \le 2{,}000{,}000{,}000$), combien de façons différentes permettent de partir d’une vache et d’obtenir $N$ vaches ? Le nombre de façons d’obtenir $N$ ne dépasse pas $2{,}000{,}000{,}000$.

Entrée

• Ligne 1 : entier $N$.

Sortie

• Ligne 1 : nombre de façons d’obtenir $N$ vaches.

Exemples

Entrée 1

12

Sortie 1

8

Remarque

Détails de la sortie

Une façon d’obtenir douze est $(2,2,3)$ : deux veaux par vache à la première génération, deux à la deuxième, trois à la troisième, soit douze jeunes veaux. Les sept autres sont $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$.

Auteur : Mihai Stroe, 2002