Problem Description

This problem is translated from CCC 2018 S4 “Balanced Trees”.

We define a “perfectly balanced tree” as follows:

Each perfectly balanced tree has a positive integer weight. A perfectly balanced tree with weight $1$ is a tree with only $1$ node. Otherwise, if the tree has weight $w(w\ge2)$, then it is a rooted tree with $k(2\le k\le w)$ subtrees. All $k$ subtrees must be the same, and all of its $k$ subtrees must be exactly identical, and each subtree itself must be perfectly balanced.

In particular, the weights of all $k$ subtrees must be the same. Their weight must be $\left\lfloor\frac{w}{k}\right\rfloor$. For example, if a perfectly balanced tree of weight $8$ has $3$ subtrees, then each subtree has weight $2$, because $2+2+2=6\le8$.

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

Input Format

The input contains one line with one integer $N$.

Output Format

Output one integer, the number of perfectly balanced trees with weight $N$.

4

3

10

13

Hint

Sample Explanation 1

The valid trees are:

• A perfectly balanced tree whose root has $4$ subtrees of weight $1$.
• A perfectly balanced tree whose root has $2$ subtrees of weight $2$.
• A perfectly balanced tree whose root has $3$ subtrees of weight $1$.

Constraints:

For $33\%$ of the testdata, $N\le1000$.
For another $13\%$ of the testdata, $N\le5\times 10^4$.
For another $13\%$ of the testdata, $N\le10^6$.
For all testdata, $1\le N\le10^9$.

Translated by ChatGPT 5