Game with String

小 A、小 B 正在玩一个猜字符串游戏。 这个游戏的规则是这样的：给定一个两人都预先知道的字符串 $S$，小 A 先让 $S$ 随机“逆时针旋转”（将最后一个字符插入到字符串首）$0\sim\lvert S\rvert-1$ 次，变为字符串 $T$。随后小 B 可以查看 $T$ 的首字母，之后他可以选择一个 $i$ 并检查 $T_i$ 以唯一确定 $T$。如果他没法确定，他就输了。 求小 B 在最优行动下获胜的概率。 保证 $\lvert S\rvert\le5000$。

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.

The only string contains the string $ s $ of length $ l $ $ (3<=l<=5000) $ , consisting of small English letters only.

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 

technocup

1.000000000000000

tictictactac

0.333333333333333

bbaabaabbb

0.100000000000000

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.