Farmer John cria vacas. Técnicas modernas usam touros premiados mortos há muito, dispensando touros. Controla o número de bezerros pela comida; todas recebem a mesma quantidade e produzem o mesmo número. Começa com uma vaca e quer $N$ após algumas gerações.

Se $N = 12$, alimenta a original para três bezerros. Quando crescem para se reproduzir, alimenta cada um para quatro, obtendo doze no fim. Vende cada vaca após produzir filhotes, mantendo apenas a geração mais recente.

Em cada geração, cada vaca produz pelo menos dois bezerros, sem limite superior, pois usa uma raça muito forte.

Para o inteiro $N$ ($1 \le N \le 2{,}000{,}000{,}000$), quantas formas diferentes permitem obter $N$ vacas começando com uma? O número de formas de obter $N$ não passa de $2{,}000{,}000{,}000$.

Entrada

• Linha 1: inteiro $N$.

Saída

• Linha 1: número de formas de obter $N$ vacas.

Exemplos

Entrada 1

12

Saída 1

8

Explicação

Detalhes da saída

Uma forma de obter doze é $(2,2,3)$: dois bezerros por vaca na primeira geração, dois na segunda e três na terceira, total doze jovens. As outras sete são $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$.

Autor: Mihai Stroe, 2002