균형 트리

트리에는 흥미로운 성질이 많다. 자연에 있는 트리뿐만 아니라 수학과 컴퓨터 과학에서 다루는 트리도 마찬가지다. 그중 완전 균형 트리(perfectly balanced tree)는 다음과 같이 정의된다.

완전 균형 트리는 모두 양의 정수 가중치를 가진다. 가중치 1인 완전 균형 트리는 항상 노드 하나로 이루어진다. 가중치가 w이고 w ≥ 2인 완전 균형 트리는 루트 노드에서 k개의 서브트리로 가지가 뻗은 형태이며, 이때 2 ≤ k ≤ w이다. 이때 k개의 서브트리는 모두 완전히 동일해야 하며, 각각도 완전 균형 트리여야 한다.

즉, k개의 서브트리는 모두 같은 가중치를 가져야 한다. 이 공통 가중치는 k개 서브트리의 가중치 합이 전체 트리의 가중치 w를 넘지 않도록 하는 최대 정수이다. 예를 들어 가중치 8인 완전 균형 트리가 서브트리 3개를 가진다면, 각 서브트리의 가중치는 2가 된다. 2 + 2 + 2 = 6 ≤ 8이기 때문이다.

N이 주어졌을 때, 가중치가 N인 완전 균형 트리의 개수를 구하시오.

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10^9)

가중치가 N인 완전 균형 트리의 개수를 정수 하나로 출력한다.