题目描述

题目译自 BalticOI 2022 Day2「Boarding Passes」

在成功遵守当地的风俗之后，你正好赶上了轮船的出发时间。然而，你没有想到会有那么多人前往吕贝克！由于你不想在颁奖仪式上迟到（你还需要一些时间将你所有偷来的艺术品存放在旅店里），你想加快轮船的登船速度。

船上有一排 $N$ 个座位，共 $N$ 名乘客预订了所有座位。每位乘客都有一张船票，上面写着他们的指定座位和 $G$ 个登船组中的一组。

登船时，一次会叫一个组的乘客登船。每个登船组内的乘客将以随机顺序登船，即对于所有可能的登船顺序，出现概率相等。每位乘客可以在第一个座位的前面或最后一个座位的后面登船，然后在另一位乘客登船前移到他们的指定座位。

你确定这个过程中，当一个乘客要经过已经入座的乘客时最耗时（装有所有这些领带的行李在过道上是一个相当大的障碍）。幸运的是，你在附近的储物柜里发现了一件工作人员的制服，所以你可以决定各组乘客的登船顺序，并在登船开始前告诉每位乘客，是要从所有座位的前面还是后面登船。

编写一个程序，利用船票信息计算出在登船过程中，如果你确定了登船组的登船顺序，并将乘客分配到最前面和后面时，一个乘客要经过已经入座的乘客的次数的最小值的期望。

注意
给定一个登船组的登船顺序，并将乘客分配到最前面和后面时，一个乘客要经过已经入座的乘客的次数的期望被定义为：

[ 1 \cdot p_1 + 2 \cdot p_2 + 3 \cdot p_3 + \ldots ]

其中 $p_k$ 是登船时一个乘客要经过已经入座的乘客的次数恰好为 $k$ 的概率。换句话说，这是每个登船组中所有可能的乘客登船顺序中一个乘客要经过已经入座的乘客的平均次数。

---

输入格式

输入包含一个由 $N$ 个字符组成的字符串 $s_1 \ldots s_N$，其中 $s_i$ 是前 $G$ 个大写英文字母中的一个，表示坐在第 $i$ 个座位的乘客所属的登船组（最前面的座位为 $1$ 号座位）。

---

输出格式

输出一个实数，表示确定了登船组的登船顺序，并将乘客分配到最前面和后面时，一个乘客要经过已经入座的乘客的次数的最小值的期望。

如果你的输出与答案的绝对误差不大于 $0.001$，则认为你的输出是正确的。

---

样例 1

输入

AACCAA

输出

1

解释
在样例一中，$C$ 组应该在 $A$ 组之前登船，第 $1,2,3$ 个座位上的乘客应该从前面登船，而其他乘客应该从后面登船。

这使得 $C$ 组的两名乘客不可能互相通过，而且他们也不会经过 $A$ 组的任何乘客，因为 $C$ 组的乘客先登船。此外，$A$ 组的乘客也不会经过 $C$ 组的任何乘客，因为所有从前面登船的 $A$ 组乘客都坐在 $C$ 组乘客的前面，所有从后面登船的 $A$ 组乘客都坐在 $C$ 组乘客的后面。

因此，唯一的可能是第 $2$ 个座位的乘客经过第 $1$ 个座位的乘客，这只会发生在第 $1$ 个座位的乘客在第 $2$ 个座位的乘客之前登船的情况下，第 $5$ 和第 $6$ 个座位的乘客也是如此。由于这些事件发生的概率都是 $50\%$，因此，经过次数的最小期望等于 $1$。

---

样例 2

输入

HEHEHEHIHILOL

输出

7.5

---

样例 3

输入

ONMLKJIHGFEDCBAABCDEFGHIJKLMNO

输出

0

---

样例 4

输入

AAAAAAAAAAAAA...AAAAAAAAAAAAAA

输出

100800.5

这组样例中共有 $899$ 个 $A$。

---

数据范围与提示

对于所有数据，满足 $1 \le G \le 15$，$1 \le N \le 10^5$。

详细子任务附加限制及分值如下表：

子任务编号	附加限制	分值
1	$G=1$，即只有一个登船组	5
2	$G \le 7, N \le 100$	25
3	$G \le 10, N \le 10\,000$	30
4	无附加限制	40