Canadian Computing Competition: 2018 Stage 1, Senior #4

Trees have many fascinating properties. While this is primarily true for trees in nature, the concept of trees in math and computer science is also interesting. A particular kind of tree, a perfectly balanced tree, is defined as follows.

Every perfectly balanced tree has a positive integer weight. A perfectly balanced tree of weight ~1~ always consists of a single node. Otherwise, if the weight of a perfectly balanced tree is ~w~ and ~w \ge 2~, then the tree consists of a root node with branches to ~k~ subtrees, such that ~2 \le k \le w~. In this case, all ~k~ subtrees must be completely identical, and be perfectly balanced themselves.

In particular, all ~k~ subtrees must have the same weight. This common weight must be the maximum integer value such that the sum of the weights of all ~k~ subtrees does not exceed ~w~, the weight of the overall tree. For example, if a perfectly balanced tree of weight ~8~ has ~3~ subtrees, then each subtree would have weight ~2~, since ~2 + 2 + 2 = 6 \le 8~.

Given ~N~, find the number of perfectly balanced trees with weight ~N~.

Input Specification

The input will be a single line containing the integer ~N~ ~(1 \le N \le 10^9)~.

For ~5~ of the ~15~ marks available, ~N \le 1\,000~.

For an additional ~2~ of the ~15~ marks available, ~N \le 50\,000~.

For an additional ~2~ of the ~15~ marks available, ~N \le 10^6~.

Output Specification

Output a single integer, the number of perfectly balanced trees with weight ~N~.

Sample Input 1

4

Sample Output 1

3

Explanation for Sample Output 1

One tree has a root with four subtrees of weight ~1~; a second tree has a root with two subtrees of weight ~2~; the third tree has a root with three subtrees of weight ~1~.

Sample Input 2

10

Sample Output 2

13