Little Elephant and Furik and Rubik

2000ms

262144K

Description:

Little Elephant loves Furik and Rubik, who he met in a small city Kremenchug.

The Little Elephant has two strings of equal length a and b, consisting only of uppercase English letters. The Little Elephant selects a pair of substrings of equal length — the first one from string a, the second one from string b. The choice is equiprobable among all possible pairs. Let's denote the substring of a as x, and the substring of b — as y. The Little Elephant gives string x to Furik and string y — to Rubik.

Let's assume that f(x, y) is the number of such positions of i (1 ≤ i ≤ |x|), that x_i = y_i (where |x| is the length of lines x and y, and x_i, y_i are the i-th characters of strings x and y, correspondingly). Help Furik and Rubik find the expected value of f(x, y).

Input:

The first line contains a single integer n (1 ≤ n ≤ 2·10⁵) — the length of strings a and b. The second line contains string a, the third line contains string b. The strings consist of uppercase English letters only. The length of both strings equals n.

Output:

On a single line print a real number — the answer to the problem. The answer will be considered correct if its relative or absolute error does not exceed 10^- 6.

Sample Input:

2
AB
BA

Sample Output:

0.400000000

Sample Input:

3
AAB
CAA

Sample Output:

0.642857143

Note:

Let's assume that we are given string a = a₁a₂... a_|a|, then let's denote the string's length as |a|, and its i-th character — as a_i.

A substring a[l... r] (1 ≤ l ≤ r ≤ |a|) of string a is string a_la_l + 1... a_r.

String a is a substring of string b, if there exists such pair of integers l and r (1 ≤ l ≤ r ≤ |b|), that b[l... r] = a.

Let's consider the first test sample. The first sample has 5 possible substring pairs: ("A", "B"), ("A", "A"), ("B", "B"), ("B", "A"), ("AB", "BA"). For the second and third pair value f(x, y) equals 1, for the rest it equals 0. The probability of choosing each pair equals $\text{[math]}$ , that's why the answer is $\text{[math]}$ · 0 + $\text{[math]}$ · 1 + $\text{[math]}$ · 1 + $\text{[math]}$ · 0 + $\text{[math]}$ · 0 = $\text{[math]}$ = 0.4.

Informação

Provedor Codeforces

Código CF204C