Problem: 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 = sk + 1sk + 2... sns1s2... sk. 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 <image>

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.

Solution (in JAVA):

Solution:
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.TreeSet;



public final class CF_468_E2 {

	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}










	// Global vars
	static BufferedWriter out;
	static InputReader reader;




	static void process() throws Exception {

		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader=new InputReader(System.in);

		String s=reader.readString();
		int L=s.length();
		int CX=26;

		ArrayList<Integer>[] pos=new ArrayList[CX];
		for (int u=0;u<CX;u++)
			pos[u]=new ArrayList<Integer>();
		for (int i=0;i<L;i++) {
			pos[s.charAt(i)-'a'].add(i);

		}


		int bob=0;

		for (int e=0;e<CX;e++){
			int[][] used=new int[L][CX];

			for (int i:pos[e]){
				for (int u=0;u<L;u++){
					int y=s.charAt((i+u)%L)-'a';
					used[u][y]++;
				}
			}
			int mx=0;
			int tgt=-1;

			for (int i=0;i<L;i++){
				int disc=0;
				for (int x:pos[e]){
					int y=s.charAt((i+x)%L)-'a';
					if (used[i][y]==1)
						disc++;
				}

				if (disc>mx){
					mx=disc;
					tgt=i;
				}

			}
			bob+=mx;
		}
		double prob=bob;
		prob/=L;
		output(prob);



		try {
			out.close();
		}
		catch (Exception EX){}


	}


	static void processKO() throws Exception {

		//log(0.75*4+3+3);
		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader=new InputReader(System.in);

		String s=reader.readString();
		int L=s.length();
		int CX=26;
		int[] cnt=new int[CX];
		for (int i=0;i<L;i++)
			cnt[s.charAt(i)-'a']++;


		char[] mem=new char[2*L];
		for (int u=0;u<2*L;u++)
			mem[u]=s.charAt(u%L);
		ArrayList<String>[] hs=new ArrayList[CX];

		int[][][] used=new int[CX][L][CX];
		int[] num=new int[CX];
		for (int i=0;i<L;i++){
			// pick shifted
			// look at begining
			// see if we can differentiate
			// start at i
			int x=mem[i]-'a';
			num[x]++;
			char[] tmp=new char[L];
			for (int u=0;u<L;u++){
				int y=mem[i+u]-'a';
				tmp[u]=mem[i+u];
				used[x][u][y]=1;
			}
			log(new String(tmp));
		}
		double prob=0;

		for (int u=0;u<CX;u++){
			if (num[u]>0){
				//log((char)(u+'a')+" "+num[u]);
				boolean found=false;
				int mdiff=0;
				lp:for (int i=0;i<L;i++){
					int diff=0;
					for (int v=0;v<CX;v++){
						if (used[u][i][v]==1)
							diff++;
					}
					mdiff=Math.max(diff,mdiff);
					if (diff==num[u]){
						found=true;
						break lp;
					}
				} 
				log("u:"+(char)(u+'a')+" found "+num[u]+" occurences and was able to separate "+mdiff);
				//double freq=num[u];
				//freq/=L;

				double freq=num[u];
				freq/=L;
				if (mdiff==num[u])
					prob+=freq;


			}
		}

		/*
		double res=win;
		res/=(win+lose);
		double min=1;
		min/=L;
		res=Math.max(res,min);
		output(res);
		 */
		output(prob);



		try {
			out.close();
		}
		catch (Exception EX){}


	}


	public static void main(String[] args) throws Exception {
		process();

	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}


		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res=new StringBuilder();
			do {
				res.append((char)c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			//log("d:"+d);
			if (d=='-') {
				neg=true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			//log("d:"+d);
			if (d=='-') {
				neg=true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}




		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}


}