27030번 - Breeding 다국어

문제

Farmer John is breeding his cows (no bulls are necessary in these days of modern breeding techniques using long-dead prize-winning bulls). By carefully choosing the amount of food they receive, Farmer John can control the number of calves each cow in his herd will produce. Since he feeds each cow the same amount, each cow will produce the same number of calves. Farmer John starts with a single cow and wants to expand to a herd of N cows after some number of generations of breeding.

For example, if N = 12, then Farmer John could feed his original cow enough to produce 3 calves. When this next generation grows old enough to produce calves, he feeds them each enough to produce 4 calves, yielding 12 cows in the final generation. Once a cow produces offspring she is sold, so Farmer John only keeps the cows in the most recent generation.

During each generation, each cow produces no fewer than 2 calves, and there is no upper limit on the number of calves a cow can have (Farmer John uses a very strong breed of cow).

Given an integer N (1 ≤ N ≤ 2,000,000,000), how many different ways can Farmer John eventually obtain N cows, if he starts with only 1? The number of ways of obtaining N will not exceed 2,000,000,000.

입력

• Line 1: The integer N.

출력

• Line 1: The number of ways to obtain N cows.

제한

힌트

One way to obtain 12 cows is (2,2,3). That is, produce 2 calves per cow in the first generation, 2 calves in the second generation, and 3 calves in the third generation (for a total of 12 young calves). The other seven ways are (2,3,2), (3,2,2), (3,4), (4,3), (12), (2,6), and (6,2).