Farmer John은 소를 번식시킵니다. 현대 기술은 오래전에 죽은 수상 황소를 활용하므로 황소가 필요 없습니다. 먹이 양으로 송아지 수를 조절합니다. 모두 같은 양을 먹여 각 소가 같은 수를 낳습니다. 한 마리에서 몇 세대 뒤 $N$마리로 늘리고 싶습니다.

$N = 12$라면 처음 소에 세 마리를 낳을 먹이를 줍니다. 다음 세대가 번식할 나이가 되면 각 소에 네 마리분을 먹여 마지막에 열두 마리를 얻습니다. 출산한 어미는 팔아 최신 세대만 남깁니다.

각 세대의 소는 최소 두 마리를 낳고 상한은 없습니다. 아주 강한 품종이기 때문입니다.

정수 $N$ ($1 \le N \le 2{,}000{,}000{,}000$)에 대해 한 마리로 시작해 $N$마리를 얻는 서로 다른 방법은 몇 개인가요? $N$마리를 얻는 방법 수는 $2{,}000{,}000{,}000$ 이하입니다.

입력

• 1번 줄: 정수 $N$.

출력

• 1번 줄: $N$마리를 얻는 방법 수.

예제

입력 1

12

출력 1

8

참고

출력 설명

열두 마리를 얻는 한 방법은 $(2,2,3)$입니다. 첫 세대 각 소 두 마리, 둘째 두 마리, 셋째 세 마리로 총 열두 송아지입니다. 다른 일곱 방법은 $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$입니다.

문제 작성: Mihai Stroe, 2002