Balanced Trees

Τα δέντρα έχουν πολλές συναρπαστικές ιδιότητες. Ενώ αυτό ισχύει πρωτίστως για τα δέντρα στη φύση, η έννοια των δέντρων στα μαθηματικά και την επιστήμη των υπολογιστών είναι επίσης ενδιαφέρουσα. Ένα ιδιαίτερο είδος δέντρου, το τέλεια ισορροπημένο δέντρο, ορίζεται ως εξής.

Κάθε τέλεια ισορροπημένο δέντρο έχει ένα θετικό ακέραιο βάρος. Ένα τέλεια ισορροπημένο δέντρο με βάρος ~1~ αποτελείται πάντα από έναν μόνο κόμβο. Διαφορετικά, αν το βάρος ενός τέλεια ισορροπημένου δέντρου είναι ~w~ και ~w \ge 2~, τότε το δέντρο αποτελείται από έναν κόμβο-ρίζα με διακλαδώσεις σε ~k~ υποδέντρα, έτσι ώστε ~2 \le k \le w~. Σε αυτή την περίπτωση, όλα τα ~k~ υποδέντρα πρέπει να είναι απολύτως όμοια και να είναι και τα ίδια τέλεια ισορροπημένα.

Ειδικότερα, όλα τα ~k~ υποδέντρα πρέπει να έχουν το ίδιο βάρος. Αυτό το κοινό βάρος πρέπει να είναι η μέγιστη ακέραια τιμή, ώστε το άθροισμα από τα βάρη όλων των ~k~ υποδέντρων να μην υπερβαίνει το ~w~, το βάρος του συνολικού δέντρου. Για παράδειγμα, αν ένα τέλεια ισορροπημένο δέντρο βάρους ~8~ έχει ~3~ υποδέντρα, τότε κάθε υποδέντρο θα έχει βάρος ~2~, αφού ~2 + 2 + 2 = 6 \le 8~.

Δεδομένου του ~N~ , βρείτε τον αριθμό των τέλεια ισορροπημένων δέντρων με βάρος ~N~.

Είσοδος

Η είσοδος θα αποτελείται από μία γραμμή που θα περιέχει τον ακέραιο αριθμό ~N\;(1 \le N \le 10^{9})~.

Για ~5~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 1000~.

Για επιπλέον ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 50000~.

Για επιπλέον ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 10^{6}~.

Έξοδος

Εξάγετε έναν ακέραιο αριθμό, τον αριθμό των τέλεια ισορροπημένων δέντρων με βάρος ~N~.

Παραδείγματα

input

4

output

3

Επεξήγηση του πρώτου παραδείγματος:

Ένα δέντρο έχει μια ρίζα με τέσσερα υποδέντρα βάρους ~1~- ένα δεύτερο δέντρο έχει μια ρίζα με δύο υποδέντρα βάρους ~2~- το τρίτο δέντρο έχει μια ρίζα με τρία υποδέντρα βάρους ~1~.

input

10

output

13