Vasya and Kolya play a game with a string, using the following rules. Initially, Kolya creates a string _s_, consisting of small English letters, and uniformly at random chooses an integer _k_ from a segment \[0, _len_(_s_) - 1\]. He tells Vasya this string _s_, and then shifts it _k_ letters to the left, i. e. creates a new string _t_ = _s__k_ + 1_s__k_ + 2... _s__n__s_1_s_2... _s__k_. Vasya does not know the integer _k_ nor the string _t_, but he wants to guess the integer _k_. To do this, he asks Kolya to tell him the first letter of the new string, and then, after he sees it, open one more letter on some position, which Vasya can choose.
Vasya understands, that he can't guarantee that he will win, but he wants to know the probability of winning, if he plays optimally. He wants you to compute this probability.
Note that Vasya wants to know the value of _k_ uniquely, it means, that if there are at least two cyclic shifts of _s_ that fit the information Vasya knowns, Vasya loses. Of course, at any moment of the game Vasya wants to maximize the probability of his win.
## Input
The only string contains the string _s_ of length _l_ (3 ≤ _l_ ≤ 5000), consisting of small English letters only.
## Output
Print the only number — the answer for the problem. You answer is considered correct, if its absolute or relative error does not exceed 10 - 6.
Formally, let your answer be _a_, and the jury's answer be _b_. Your answer is considered correct if
[samples]
## Note
In the first example Vasya can always open the second letter after opening the first letter, and the cyclic shift is always determined uniquely.
In the second example if the first opened letter of _t_ is "_t_" or "_c_", then Vasya can't guess the shift by opening only one other letter. On the other hand, if the first letter is "_i_" or "_a_", then he can open the fourth letter and determine the shift uniquely.
Let $ s $ be a string of length $ l $, with characters indexed from $ 0 $ to $ l-1 $. Let $ k \in \{0, 1, \dots, l-1\} $ be chosen uniformly at random. Define the cyclic shift $ t^{(k)} $ of $ s $ by $ k $ positions to the left as:
$$
t^{(k)}_i = s_{(i + k) \mod l}, \quad \text{for } i = 0, 1, \dots, l-1.
$$
Vasya is told $ s $, and observes the first character of $ t^{(k)} $, i.e., $ t^{(k)}_0 = s_k $. Based on this, he chooses a position $ p \in \{1, 2, \dots, l-1\} $ to query the character $ t^{(k)}_p = s_{(p + k) \mod l} $.
Let $ A = \{ k \in \{0, \dots, l-1\} \mid s_k = c_0 \} $, where $ c_0 $ is the first character observed. For each candidate $ k \in A $, the pair $ (c_0, c_p) $ must uniquely determine $ k $, i.e., for any two distinct $ k_1, k_2 \in A $, it must hold that:
$$
s_{(p + k_1) \mod l} \ne s_{(p + k_2) \mod l}.
$$
Vasya chooses $ p $ to maximize the probability that $ | \{ k \in A \mid \text{the pair } (s_k, s_{(p+k) \mod l}) \text{ uniquely identifies } k \} | = |A| $, i.e., that all candidates consistent with the first character become distinguishable after querying position $ p $.
Let $ P $ be the probability that Vasya wins when playing optimally.
Define, for each $ c \in \Sigma $ (alphabet), the set:
$$
A_c = \{ k \in \{0, \dots, l-1\} \mid s_k = c \}.
$$
For each $ c \in \Sigma $, and for each possible query position $ p \in \{1, \dots, l-1\} $, define the mapping:
$$
f_{c,p}(k) = s_{(p + k) \mod l}, \quad \text{for } k \in A_c.
$$
Let $ N_{c,p} $ be the number of distinct values in the multiset $ \{ f_{c,p}(k) \mid k \in A_c \} $. Then, the number of $ k \in A_c $ that are uniquely identifiable under query $ p $ is exactly $ N_{c,p} $, since each distinct output corresponds to exactly one $ k \in A_c $ (by injectivity of $ f_{c,p} $ on the preimage).
Thus, for fixed $ c $, the maximum number of identifiable shifts over all $ p $ is:
$$
M_c = \max_{p \in \{1,\dots,l-1\}} N_{c,p}.
$$
The probability of winning is then:
$$
P = \frac{1}{l} \sum_{c \in \Sigma} |A_c| \cdot \frac{M_c}{|A_c|} = \frac{1}{l} \sum_{c \in \Sigma} M_c.
$$
That is, for each character $ c $, if it appears $ |A_c| $ times as the first character, then Vasya can uniquely identify $ M_c $ of the possible shifts $ k $ for which $ s_k = c $, by choosing the best $ p $. The total probability is the average over all $ l $ possible $ k $, weighted by the number of $ k $ that become uniquely identifiable.
---
**Final Formal Statement:**
Let $ s \in \Sigma^l $, $ \Sigma = \{a, b, \dots, z\} $, $ l \ge 3 $.
For each character $ c \in \Sigma $, define:
- $ A_c = \{ k \in \{0, 1, \dots, l-1\} \mid s_k = c \} $
- For each $ p \in \{1, 2, \dots, l-1\} $, define $ f_{c,p}(k) = s_{(k + p) \mod l} $ for $ k \in A_c $
- Let $ N_{c,p} = \left| \{ f_{c,p}(k) \mid k \in A_c \} \right| $ (number of distinct values)
- Let $ M_c = \max_{p \in \{1,\dots,l-1\}} N_{c,p} $
Then the optimal win probability is:
$$
\boxed{P = \frac{1}{l} \sum_{c \in \Sigma} M_c}
$$