Вася и Коля играют в игру со строкой по следующим правилам. Сначала Коля загадывает строку s, состоящую из строчных латинских букв, и равновероятно выбирает из отрезка [0, len(s) - 1] целое число k. Он сообщает строку s Васе, а затем циклически сдвигает её на k символов влево, то есть получает новую строку t = sk + 1sk + 2... sns1s2... sk. Вася не знает ни числа k, ни итоговой строки t, но хочет угадать число k. Для этого он может попросить Колю открыть первую букву получившейся строки, а затем, увидев её, еще одну букву на некоторой позиции, которую Вася может выбрать.
Вася уже понял, что не может гарантировать себе победу, однако, он хочет узнать вероятность своего выигрыша при оптимальной игре. Вам необходимо помочь ему в этом.
Заметим, что целью Васи является однозначное определение числа k, значит, если после открытия второй буквы остается не менее двух циклических сдвигов исходной строки s, удовлетворяющих известной информации, Вася считается проигравшим. Конечно же, в каждый момент игры Вася пытается максимизировать вероятность своего выигрыша, насколько это возможно.
Единственна строка содержит строку s длины l (3 ≤ l ≤ 5000), состоящую из строчных латинских букв.
Выведите одно вещественное число — ответ на задачу. Ответ будет считаться верным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
Формально, пусть ваш ответ равен a, а ответ жюри — b. Ваш ответ считается правильным, если 
.
technocup
1.000000000000000
tictictactac
0.333333333333333
bbaabaabbb
0.100000000000000
В первом примере после открытия первой буквы Вася может попросить открыть вторую букву, и после этого циклический сдвиг определяется однозначно.
Во втором примере если первой буквой в циклическом сдвиге t будет «t» или «c», то у Васи не получится угадать сдвиг, открыв лишь одну другую букву. В то же время, если первой буквой будет «i» или «a», то, открыв четвертую букву, можно однозначно определить циклический сдвиг.
