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.
Vasya 和 Kolya 玩一个关于字符串的游戏，规则如下：最初，Kolya 创建一个由小写英文字母组成的字符串 #cf_span[s]，并从区间 #cf_span[[0, len(s) - 1]] 中均匀随机选择一个整数 #cf_span[k]。他将字符串 #cf_span[s] 告诉 Vasya，然后将其向左移动 #cf_span[k] 个字符，即生成一个新字符串 #cf_span[t = sk + 1sk + 2... sns1s2... sk]。Vasya 不知道整数 #cf_span[k]，也不知道字符串 #cf_span[t]，但他希望猜出 #cf_span[k]。为此，他要求 Kolya 告诉他新字符串的第一个字母，然后在看到该字母后，选择另一个位置打开一个额外的字母。
Vasya 明白他不能保证一定能赢，但他想知道在最优策略下获胜的概率。你需要计算这个概率。
注意，Vasya 希望唯一确定 #cf_span[k] 的值；这意味着，如果存在至少两个 #cf_span[s] 的循环移位与 Vasya 已知的信息一致，则 Vasya 失败。当然，在游戏的任何时刻，Vasya 都会最大化自己获胜的概率。
输入仅包含一个长度为 #cf_span[l] #cf_span[(3 ≤ l ≤ 5000)] 的字符串 #cf_span[s]，仅由小写英文字母组成。
请输出一个数字——本题的答案。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。
形式上，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，你的答案被认为是正确的当且仅当
在第一个示例中，Vasya 总可以在打开第一个字母后打开第二个字母，此时循环移位总是能唯一确定。
在第二个示例中，若 #cf_span[t] 的第一个打开字母是 "_t_" 或 "_c_"，则 Vasya 仅通过再打开一个字母无法确定移位；而若第一个字母是 "_i_" 或 "_a_"，他可以打开第四个字母并唯一确定移位。
## Input
输入仅包含一个长度为 #cf_span[l] #cf_span[(3 ≤ l ≤ 5000)] 的字符串 #cf_span[s]，仅由小写英文字母组成。
## Output
请输出一个数字——本题的答案。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。形式上，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，你的答案被认为是正确的当且仅当
[samples]
## Note
在第一个示例中，Vasya 总可以在打开第一个字母后打开第二个字母，此时循环移位总是能唯一确定。
在第二个示例中，若 #cf_span[t] 的第一个打开字母是 "_t_" 或 "_c_"，则 Vasya 仅通过再打开一个字母无法确定移位；而若第一个字母是 "_i_" 或 "_a_"，他可以打开第四个字母并唯一确定移位。
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 $ t^{(k)}_0 $ (the first character of the shifted string).
Then, he chooses an index $ j \in \{1, 2, \dots, l-1\} $ to observe $ t^{(k)}_j $.
He wins if, given $ (t^{(k)}_0, t^{(k)}_j) $, there is a **unique** $ k' \in \{0, \dots, l-1\} $ such that:
$$
s_{k'} = t^{(k)}_0 \quad \text{and} \quad s_{(j + k') \mod l} = t^{(k)}_j.
$$
Vasya chooses $ j $ **after** seeing $ t^{(k)}_0 $, to maximize the probability of uniquely identifying $ k $.
We compute the **maximum probability of winning** over all optimal strategies.
---
**Formal Definition:**
Let $ \mathcal{K} = \{0, 1, \dots, l-1\} $.
For each $ c \in \Sigma $ (alphabet of lowercase letters), define:
$$
A_c = \{ k \in \mathcal{K} \mid s_k = c \}
$$
— the set of possible shifts that produce first character $ c $.
For a fixed $ c $, Vasya chooses $ j \in \{1, \dots, l-1\} $ to maximize the number of $ k \in A_c $ that are uniquely identifiable via $ t^{(k)}_j = s_{(j + k) \mod l} $.
For a fixed $ j $, define the equivalence relation on $ A_c $:
$$
k_1 \sim_j k_2 \iff s_{(j + k_1) \mod l} = s_{(j + k_2) \mod l}
$$
Then, the number of uniquely identifiable shifts under $ j $ is:
$$
U_j(c) = \left| \left\{ k \in A_c \mid \forall k' \in A_c \setminus \{k\},\ s_{(j + k) \mod l} \ne s_{(j + k') \mod l} \right\} \right|
$$
Vasya chooses $ j $ to maximize $ U_j(c) $. So for each $ c $, define:
$$
U^*(c) = \max_{j \in \{1, \dots, l-1\}} U_j(c)
$$
The total winning probability is:
$$
P = \frac{1}{l} \sum_{k=0}^{l-1} \mathbf{1}\left[ \text{the shift } k \text{ is uniquely identifiable after observing } s_k \text{ and optimally chosen } j \right]
$$
But since $ k $ is uniform and $ s_k = c $, we group by character:
$$
P = \sum_{c \in \Sigma} \frac{|A_c|}{l} \cdot \frac{U^*(c)}{|A_c|} = \sum_{c \in \Sigma} \frac{U^*(c)}{l}
$$
---
**Final Formal Statement:**
Given a string $ s $ of length $ l $, compute:
$$
\boxed{P = \frac{1}{l} \sum_{c \in \Sigma} U^*(c)}
$$
where for each character $ c \in \Sigma $,
- $ A_c = \{ k \in \{0, \dots, l-1\} \mid s_k = c \} $,
- $ U^*(c) = \max_{j=1}^{l-1} \left| \left\{ k \in A_c \mid \forall k' \in A_c \setminus \{k\},\ s_{(j + k) \mod l} \ne s_{(j + k') \mod l} \right\} \right| $
This is the maximum probability that Vasya can win by optimally choosing the second position to reveal.