小象很喜欢福里克和鲁比克,他们是他在小城市克列缅楚格认识的。
小象有两个长度相等的字符串a和b,仅由大写英文字母组成。小象选择一对长度相等的子串——第一个来自字符串 a,第二个来自字符串 b。在所有可能的对中,选择的概率是相等的。我们将 a 的子串表示为 x,将 b 的子串表示为 y。小象把字符串 x 给了福里克,把字符串 y 给了鲁比克。
假设 f(x, y) 是 i (1 ≤ i ≤ |x|) 的位置数,即 xi = yi(其中 |x| 是 x 和 y 行的长度,xi、yi 分别是字符串 x 和 y 的第 i 个字符)。帮助 Furik 和 Rubik 求 f(x, y) 的期望值。
输入
第一行包含一个整数 n (1 ≤ n ≤ 2·105) — 字符串 a 和 b 的长度。第二行包含字符串a,第三行包含字符串b。字符串仅由大写英文字母组成。两个字符串的长度都等于n。
输出
在一行上打印一个实数——问题的答案。如果答案的相对误差或绝对误差不超过 10 - 6,则认为答案是正确的。
示例
输入 #1
2 AB BA
输出 #1
0.400000000
输入 #2
3 AAB CAA
输出 #2
0.642857143
注意
假设给定字符串 a = a1a2... a|a|,然后将字符串的长度表示为 |a|,将其第 i 个字符表示为 ai。
字符串 a 的子串 a[l... r] (1 ≤ l ≤ r ≤ |a|) 是字符串 alal + 1... ar。
字符串 a 是字符串 b 的子字符串,如果存在整数对 l 和 r (1 ≤ l ≤ r ≤ |b|),则 b[l...r] = a。
让我们考虑第一个测试样本。第一个样本有 5 个可能的子字符串对:("A", "B")、("A", "A")、("B", "B")、("B", "A")、("AB", "BA")。对于第二对和第三对值 f(x, y) 等于 1,对于其余的值等于 0。选择每对的概率等于 $$\frac{1}{5}$$,这就是为什么答案是 $$\frac{1}{5}$$ · 0 + $$\frac{1}{5}$$ · 1 + $$\frac{1}{5}$$ · 1 + $$\frac{1}{5}$$ · 0 + $$\frac{1}{5}$$ · 0 = $$\frac{2}{5}$$ = 0.4。