Description
English:
Treeshavemanyfascinatingproperties. Whilethisisprimarilytruefortreesinnature,theconcept 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 ≥ 2, then the tree consists of a root node with branches to k subtrees, such that 2 ≤ k ≤ w. In this case, all k subtrees must be completely identical, and be perfectly balanced themselves.
Inparticular,allk subtreesmusthavethesameweight. Thiscommonweightmustbethemaximum 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 ≤ 8.
Given N, find the number of perfectly balanced trees with weight N.
Chinese:
我们定义「完美平衡树」如下：
每棵完美平衡树都有一个正整数权值。权值为 1 的完美平衡树为只含有 1 个节点的树。否则，这棵树的权值为 w(w≥2)，则这棵树为一棵含有 k(2≤k≤w) 棵子树的有根树。所有的 k棵子树都必须是相同的，且它的所有 k棵子树必须完全相同，且自身是完美平衡的。
特别是，所有的子树都具有相同的重量。 此公共权重必须为最大整数值，以使所有k个子树的权重之和不超过整个树的权重w。 例如，如果权重为8的完全平衡树具有3个子树，则每个子树将具有权重2，因为2 + 2 + 2 = 6≤8。
给定 N，求出权值为 N 的完美平衡树的数量。
Input
The input will be a single line containing the integer N (1≤N≤109)
For 5 of the 15 marks available, N≤1000
For an additional 2 of the 15 marks available, N≤50000
For an additional 2 of the 15 marks available, N≤106
输入是包含一个整数N（1≤N≤109）
对于33%的数据，N≤1000
对于另外13%的数据，N≤50000
对于额外13%的数据，N≤106
Output
Output a single integer, the number of perfectly balanced trees with weight N.
输出单个整数，即权重为N的完美平衡树的数量。
HINT
One tree has a root with four subtrees of weight 11; a second tree has a root with two subtrees of weight 22; the third tree has a root with three subtrees of weight 11.
一棵树的根具有四个权重为1的子树； 第二棵树的根具有两个权重为2的子树。 第三棵树的根包含三个权重为1的子树。