Let and be strings consisting of the English lowercase alphabet. We say that a string is a subsequence of a string if there exists a strictly increasing sequence of integers , where , and for all . Here, denotes the -th character of the string . Let denote the suffix . If , then is the empty string denoted by .
Given a nonempty string and a positive integer , we define the -set of to be the set of subsequences of whose lengths are . This implies that, for any string , the empty string belongs to by definition.
For example, when , we have .
For a string , we define the rank of to be the minimum integer such that the -sets for all suffixes of are all different. In other words, the rank of is .
For instance, when , the 2-sets and are equal. On the other hand, for , we have
Therefore, the rank of the string is 3.
Given a string , write a program to output its rank.
输入格式
Your program is to read from standard input. The input consists of a single nonempty string , which consists only of lowercase characters from the English alphabet. The length of the string is at most .
输出格式
Your program is to write to standard output. Print exactly one line. The line should contain a positive integer to represent the rank of the input string .
