Balanced Trees

Time limit2sMemory limit512 MB

Summary

Count perfectly balanced trees of weight N, where a tree splits into k identical subtrees each of the largest weight summing within the parent's weight.

Level: Medium7 of 10
Topics: Tree, Number theory, Dynamic programming, Recursion
Solved: No attempts yet

Problem

Trees have many interesting properties. This holds not only for trees in nature; trees in mathematics and computer science are interesting too. One particular kind of tree, the 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, where 2 ≤ k ≤ w. All k subtrees must be completely identical, and each must be perfectly balanced itself.

In particular, all k subtrees must have the same weight. This common weight must be the largest integer such that the sum of the weights of all k subtrees does not exceed w, the weight of the whole tree. For example, if a perfectly balanced tree of weight 8 has 3 subtrees, each subtree has weight 2, since 2 + 2 + 2 = 6 ≤ 8.

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

Input

The input consists of a single line containing the integer N. (1 ≤ N ≤ 10^9)

Output

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

Examples2

Example 1
Input
```
4
```
Expected output
```
3
```
Example 2
Input
```
10
```
Expected output
```
13
```