Problem 1037. -- 字符串拉伸

1037: 字符串拉伸

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 14  Solved: 6
[Submit][Status][Web Board]

Description

有一个字符串“0123456789”,长度为10个字符,现在你要把它拉伸成一个长度为L的字符串,拉伸的规则是把每个字符由单个变成连续的一段,例如“0001111122333344556788999”就是一个拉伸后的字符串,它的长度为25,其中,出现次数最多的字符是‘1’,共5次,出现次数最少的字符是‘6’(或‘7’),只有1次。
所谓的均匀拉伸是指:拉伸以后的字符串中,出现次数最少的字符和出现次数最多的字符,它们的出现次数之差不超过1。比如下面这个字符串就是一个长度为25的均匀拉伸:
0001122233445556677888999
对于给定的长度L,符合均匀拉伸的字符串可能有多个,例如下面这个字符串和上面的不同,但也是一个长度为25的均匀拉伸:
0011223344555666777888999
你的任务就是,给定L,统计有多少种不同的均匀拉伸。

Input

一个整数L(10<=L<=2*109)。

Output

输出一个整数C,表示长度为L的不同均匀拉伸字符串共有C个。

Sample Input

11

Sample Output

10

HINT

Source

[Submit][Status]