CF930B.Game with String

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.

瓦西娅和科里亚用一个字符串进行游戏，规则如下：首先，科里亚构造一个仅由小写英文字母组成的字符串 $s$，并从区间 $[0,\ \text{len}(s)-1]$ 中均匀随机地选择一个整数 $k$。他将字符串 $s$ 告知瓦西娅，然后将 $s$ 向左循环移动 $k$ 位，即构造新字符串

$$t = s_{k+1}s_{k+2}\dots s_{n}s_1s_2\dots s_k.$$

瓦西娅既不知道整数 $k$，也不知道字符串 $t$，但他希望猜出 $k$ 的值。为此，他向科里亚提出两个询问：

1. 请求科里亚告知新字符串 $t$ 的第一个字母；
2. 在看到该字母后，再请求科里亚打开 $t$ 中某一位置上的字母，该位置由瓦西娅自主选定。

瓦西娅明白自己无法保证必胜，但他希望知道：若采取最优策略，其获胜概率是多少？请你计算该概率。

注意：瓦西娅的目标是唯一确定 $k$ 的值。也就是说，若存在至少两个不同的循环移位（即至少两个不同的 $k'$ 值）使得对应的字符串 $t'$ 都与瓦西娅所获知的信息（即 $t$ 的首字母及他指定位置的字母）一致，则瓦西娅判负。当然，在游戏的每一步中，瓦西娅都希望最大化自己的获胜概率。

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

唯一字符串包含长度为 $l$（$3 \leq l \leq 5000$）的字符串 $s$，且 $s$ 仅由小写英文字母组成。

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

输出唯一的数字——该问题的答案。若您的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

形式化地，设您的答案为 $a$，评测组的答案为 $b$。当满足

时，您的答案被视为正确。

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.

在第一个例子中，瓦西娅总能在打开第一个字母后立即打开第二个字母，且循环移位总是唯一确定的。

在第二个例子中，若字符串 $t$ 的第一个被打开的字母是 “t” 或 “c”，则瓦西娅仅通过再打开一个字母无法确定移位量；另一方面，若第一个字母是 “i” 或 “a”，则他可以打开第四个字母，并唯一确定该移位量。