String Rank

문제

Let $ww$ and $uu$ be strings consisting of the English lowercase alphabet. We say that a string $uu$ is a subsequence of a string $ww$ if there exists a strictly increasing sequence of integers $i_1,\cdots ,i_{k}i\_1,\; \backslash cdots\; ,\; i\_k$, where $\mathrm{\mid }w\mathrm{\mid }=n|w|\; =\; n$, $\mathrm{\mid }u\mathrm{\mid }=k|u|\; =\; k$ and $u[j]=w[i_j]u[j]\; =\; w[i\_j]$ for all $j=1,\dots ,kj\; =\; 1,\; \backslash dots\; ,\; k$. Here, $v[i]v[i]$ denotes the $ii$-th character of the string $vv$. Let $w[i:]w[i:]$ denote the suffix $w[i]\cdots w[n]w[i]\; \backslash cdots\; w[n]$. If $i>ni\; >\; n$, then $w[i:]w[i:\; ]$ is the empty string denoted by $\lambda \backslash lambda$.

Given a nonempty string $ww$ and a positive integer $kk$, we define the $kk$-set of $ww$ to be the set $Q_k(w)Q\_k(w)$ of subsequences of $ww$ whose lengths are $0,1,\cdots ,k0,\; 1,\; \backslash cdots\; ,\; k$. This implies that, for any string $ww$, the empty string $\lambda \backslash lambda$ belongs to $Q_k(w)Q\_k(w)$ by definition.

For example, when $w=w\; =$aaba, we have $Q_3(Q\_3($aaba$)=\{\lambda )\; =\; \backslash \{\backslash lambda$, a, b, ba, ab, aa, aba, aab, aaa$\}\backslash \}$.

For a string $ww$, we define the rank of $ww$ to be the minimum integer $tt$ such that the $tt$-sets for all suffixes of $ww$ are all different. In other words, the rank of $ww$ is \min\{t &ge; 1 | Q_t(w[i:]) \ne Q_t(w[j:]), &forall;1 &le; i < j &le; 𝑛\}.

For instance, when $w=w\; =$aaba, the $22$-sets $Q_2(Q\_2($aba$))$ and $Q_2(Q\_2($aaba$))$ are equal. On the other hand, for $t=3t\; =\; 3$, we have

• $Q_3(\lambda )=\{\lambda \}Q\_3(\backslash lambda)\; =\; \backslash \{\backslash lambda\backslash \}$,
• $Q_3(Q\_3($a$)=\{\lambda )\; =\; \backslash \{\backslash lambda$, a$\}\backslash \}$,
• $Q_3(Q\_3($ba$)=\{\lambda )\; =\; \backslash \{\backslash lambda$, a, b, ba$\}\backslash \}$,
• $Q_3(Q\_3($aba$)=\{\lambda )\; =\; \backslash \{\backslash lambda$, a, b, ba, ab, aa, aba$\}\backslash \}$,
• $Q_3(Q\_3($aaba$)=\{\lambda )\; =\; \backslash \{\backslash lambda$, a, b, ba, ab, aa, aba, aab, aaa$\}\backslash \}$.

Therefore, the rank of the string $w=w\; =$aaba is $33$.

Given a string $ww$, write a program to output its rank.

입력

Your program is to read from standard input. The input consists of a single nonempty string $ww$, which consists only of lowercase characters from the English alphabet. The length of the string is at most $3\times {10}^{6}3\; \backslash times\; 10^6$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain a positive integer to represent the rank $tt$ of the input string $ww$.

aabbb

3

abacb

2

azadzzadaz

4

a

1