题目描述
农夫约翰在繁殖他的奶牛们。通过调整饲料的量,约翰可以控制他的牛群中每头母牛所生的小牛的数量。也就是说,他给每头奶牛喂了相同量的饲料,她们就产下了相同数量的牛犊。约翰开始是喂了一头母牛,希望通过若干代的繁殖得到N只奶牛。
比如:假如N=12,那么约翰应该喂那只最初的奶牛足够的饲料,使其生3只牛犊。当下一代的牛长大了,他就给她们喂足够的饲料,使它们生产4只牛犊,从而最后一代中有12只牛了。牛一旦生产了,约翰就把她卖了,所以,农场里只保留最新一代的牛。
每头牛生牛犊不少于2只,且无上限。
给你一个N(1<=n<=2,000,000,000),约翰可以通过多少种不同的方式使最终牛的总数为N?方法的总数量不超过2,000,000,000.
输入格式
一行:整数N。
输出格式
一行:获得N头牛的方式总数。
样例输入
样例输出