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} + 1s_{k} + 2... s_{n}s_1s_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 $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-6}$


-----Examples-----
Input
technocup

Output
1.000000000000000

Input
tictictactac

Output
0.333333333333333

Input
bbaabaabbb

Output
0.100000000000000



-----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.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Implementation

Probability

Starter code:

Solutions:
s = input()
l = len(s)
instances = [[] for x in range(26)]
s_i = [ord(c) - 97 for c in s]
for i in range(l):
	instances[s_i[i]].append(i)
sum_probability = 0
for c in range(0, 26):
	if not instances[c]:
		continue
	if len(instances[c]) == 0:
		sum_probability += 1
		continue
	max_probability = 0
	for guess in range(1, l):
		num_seen = [0] * 26
		probability = 0
		for index in instances[c]:
			num_seen[s_i[(index + guess) % l]] += 1
		for x in num_seen:
			if x == 1:
				probability += 1
		max_probability = max(max_probability, probability)
	sum_probability += max_probability
print(sum_probability / l)


s = input()

def uniq(iii):
	tmp = 0
	for jj in range(1, len(s)):
		bb = {}
		for ii in iii:
			bb.setdefault(s[ii - jj], []).append(ii)
		tmp = max(tmp, sum((1 for vvv in bb.values() if len(vvv) == 1)))
	return tmp
aa = {}
for (ii, ss) in enumerate(s):
	aa.setdefault(ss, []).append(ii)
ans = 0
for iii in aa.values():
	ans += uniq(iii)
print(ans / len(s))


s = input()
d = dict()
mod = []
mx = []
for k in s:
	d[k] = []
for i in range(len(s)):
	d[s[i]].append(i)
index = 0
for k in d.keys():
	mod.append(d[k])
for k in mod:
	mxct = 0
	ct = 0
	x = []
	for i in range(len(s)):
		ct = 0
		dic = dict()
		for j in k:
			elt = s[(j + i) % len(s)]
			if elt in dic:
				dic[elt] += 1
			else:
				dic[elt] = 1
		for r in dic:
			if dic[r] == 1:
				ct += 1
		mxct = max(ct, mxct)
	mx.append(mxct)
sm = 0
for k in mx:
	sm += k
print(sm / len(s))


str = input()
l = len(str)
a = []
for c in str:
	a.append(ord(c) - ord('a'))
a *= 2
tot = [[0] * l for i in range(26)]
for i in range(1, l):
	cnt = [[0] * 26 for i in range(26)]
	for j in range(l):
		cnt[a[j]][a[j + i]] += 1
	for j in range(l):
		if cnt[a[j]][a[j + i]] == 1:
			tot[a[j]][i] += 1
ans = 0
for sub in tot:
	ans += max(sub)
print(ans / l)


str = input()
l = len(str)
a = [0] * (2 * l)
pos = [[] for i in range(26)]
for (i, c) in enumerate(str):
	t = ord(c) - ord('a')
	a[i] = t
	a[i + l] = t
	pos[t].append(i)
ans = 0
for c in range(26):
	cur = 0
	for k in range(1, l):
		cnt = [0] * 26
		for i in pos[c]:
			cnt[a[i + k]] += 1
		tot = 0
		for i in cnt:
			if i == 1:
				tot += 1
		cur = max(cur, tot)
	ans += cur
print(ans / l)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
s = input()
l = len(s)
instances = [[] for x in range(26)]
s_i = [ord(c) - 97 for c in s]
for i in range(l):
	instances[s_i[i]].append(i)
sum_probability = 0
for c in range(0, 26):
	if not instances[c]:
		continue
	if len(instances[c]) == 0:
		sum_probability += 1
		continue
	max_probability = 0
	for guess in range(1, l):
		num_seen = [0] * 26
		probability = 0
		for index in instances[c]:
			num_seen[s_i[(index + guess) % l]] += 1
		for x in num_seen:
			if x == 1:
				probability += 1
		max_probability = max(max_probability, probability)
	sum_probability += max_probability
print(sum_probability / l)


str = input()
l = len(str)
a = [0] * (2 * l)
pos = [[] for i in range(26)]
for (i, c) in enumerate(str):
	t = ord(c) - ord('a')
	a[i] = t
	a[i + l] = t
	pos[t].append(i)
ans = 0
for c in range(26):
	cur = 0
	for k in range(1, l):
		cnt = [0] * 26
		for i in pos[c]:
			cnt[a[i + k]] += 1
		cur = max(cur, len(list(filter(lambda x: x == 1, cnt))))
	ans += cur
print(ans / l)


s = input()
n = len(s)
d = {}
for i in range(n):
	if s[i] not in d:
		d[s[i]] = []
	d[s[i]].append(s[i + 1:] + s[:i])
res = 0
for (k, l) in d.items():
	ans = 0
	for j in range(n - 1):
		(seen, s1) = (set(), set())
		for i in range(len(l)):
			if l[i][j] in s1:
				s1.remove(l[i][j])
			elif l[i][j] not in seen:
				s1.add(l[i][j])
				seen.add(l[i][j])
		ans = max(ans, len(s1))
	ans /= n
	res += ans
print('{:.7f}'.format(res))


s = input()
n = len(s)
sett = {}
for i in range(n):
	if s[i] not in sett:
		sett[s[i]] = []
	sett[s[i]].append(s[i + 1:] + s[:i])
ans = 0
for (k, l) in list(sett.items()):
	tmp = 0
	for j in range(n - 1):
		(seen, sett1) = (set(), set())
		for i in range(len(l)):
			if l[i][j] in sett1:
				sett1.remove(l[i][j])
			elif l[i][j] not in seen:
				sett1.add(l[i][j])
				seen.add(l[i][j])
		tmp = max(tmp, len(sett1))
	tmp /= n
	ans += tmp
print('{:.7}'.format(ans))


s = input()
n = len(s)
pos = [[] for i in range(26)]
for i in range(len(s)):
	pos[ord(s[i]) - 97].append(s[i:] + s[:i])
ans = 0
for i in range(26):
	max1 = 0
	for j in range(n):
		b = [0 for i in range(26)]
		for k in pos[i]:
			b[ord(k[j]) - 97] += 1
		temp1 = 0
		for k in range(26):
			if b[k] == 1:
				temp1 += 1
		max1 = max(temp1, max1)
	ans += max1
print(ans / n)


import sys
from collections import defaultdict
s = sys.stdin.readline().strip()
n = len(s)
s_mp = defaultdict(list)
for i in range(n):
	s_mp[s[i]].append(i)
result = 0
for (let, starts) in s_mp.items():
	max_p = 0.0
	for j in range(1, n):
		cnter = defaultdict(int)
		for start in starts:
			cnter[s[(start + j) % n]] += 1
		uniq = 0
		for (i, v) in cnter.items():
			if v == 1:
				uniq += 1
		max_p = max(max_p, uniq / len(starts))
		total = len(starts)
	result += max_p * len(starts) / n
print('{:.8f}'.format(result))


s = str(input())
n = len(s)
t = s + s
P = [[[0] * 26 for i in range(26)] for j in range(n)]
for i in range(n):
	c1 = ord(t[i]) - ord('a')
	for j in range(1, n):
		c2 = ord(t[i + j]) - ord('a')
		P[j][c1][c2] += 1
s = set(s)
ans = 0
for c1 in s:
	c1 = ord(c1) - ord('a')
	M = 0
	for j in range(1, n):
		temp = 0
		for c2 in range(26):
			if P[j][c1][c2] == 1:
				temp += 1
		M = max(M, temp)
	ans += M
print(ans / n)


def func(a):
	b = [0] * 26
	for i in range(len(a)):
		b[ord(a[i]) - ord('a')] += 1
	c = 0
	for i in b:
		if i == 1:
			c = c + 1
	return c
s = input()
n = len(s)
a = {}
for i in range(n):
	a[s[i]] = []
for i in range(n):
	a[s[i]].append(i)
c = 0
for i in a:
	if len(a[i]) == 1:
		c = c + 1
	else:
		e = []
		for j in range(n):
			b = []
			d = 0
			for k in a[i]:
				b.append(s[(k + j) % n])
			d = d + func(b)
			e.append(d)
		c = c + max(e)
print(c / n)