Farmer John rozmnaża krowy. Nowoczesne techniki wykorzystują dawno zmarłe nagradzane byki, więc byki nie są potrzebne. Ilością pokarmu kontroluje liczbę cieląt; każda dostaje tyle samo i rodzi tyle samo. Z jednej krowy chce po kilku pokoleniach uzyskać $N$.

Jeśli $N = 12$, karmi pierwszą dla trzech cieląt. Kiedy kolejne pokolenie dorośnie, każdą karmi dla czterech, otrzymując dwanaście. Matka po potomstwie jest sprzedawana; zostaje tylko najnowsze pokolenie.

W każdym pokoleniu każda krowa rodzi co najmniej dwa cielęta, bez górnej granicy, dzięki bardzo silnej rasie.

Dla całkowitej liczby $N$ ($1 \le N \le 2{,}000{,}000{,}000$), ile różnych sposobów prowadzi od jednej krowy do $N$? Liczba sposobów uzyskania $N$ nie przekroczy $2{,}000{,}000{,}000$.

Wejście

• Wiersz 1: całkowite $N$.

Wyjście

• Wiersz 1: liczba sposobów uzyskania $N$ krów.

Przykład

Wejście 1

12

Wyjście 1

8

Uwagi

Objaśnienie wyjścia

Sposób na dwanaście to $(2,2,3)$: po dwa cielęta na krowę w pierwszym pokoleniu, dwa w drugim, trzy w trzecim, razem dwanaście młodych cieląt. Pozostałe siedem: $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$.

Autor: Mihai Stroe, 2002