题目描述

Binary Casino 中最受欢迎的游戏之一叫作 The Binary Generator。

游戏由多名玩家使用一枚硬币进行。

首先，每名玩家选择一个由正面和反面组成的序列，所有玩家选择的序列长度相同。

随后，玩家或赌场开始不断抛掷硬币，并依次记录每次抛掷的结果。

当某名玩家选择的序列第一次作为连续子串出现在已经得到的抛掷结果中时，这名玩家获胜，游戏立即结束。

你原本认为所有序列都同样优秀，因此选择哪个序列并不重要。然而，在输光所有钱后，你开始怀疑这个想法。

给定若干个长度相同的正反面序列，请计算：从开始抛掷硬币，到至少一个给定序列首次作为连续子串出现为止，需要抛掷硬币次数的期望值。

硬币是公平的，每次抛掷：

• 得到正面 H 的概率为 $\frac12$；
• 得到反面 T 的概率为 $\frac12$；
• 各次抛掷相互独立。

期望抛掷次数可以理解为：对所有最终使某名玩家获胜的可能抛掷序列，将其长度按照该序列出现的概率加权平均。

输入格式

第一行包含两个整数 $W,B$：

分别表示玩家选择的序列数量，以及每个序列的长度。

接下来 $W$ 行，每行包含一个长度为 $B$ 的字符串。

每个字符串只由以下两个字符组成：

• H：硬币正面；
• T：硬币反面。

输出格式

输出一个实数，表示直到任意一个给定序列首次出现为止，所需抛掷硬币次数的期望值。

当输出值与正确答案的绝对误差不超过 $0.1$ 时，答案会被判定为正确。

样例 1

输入

1 1
H

输出

2.0

样例 2

输入

2 3
HHT
THT

输出

5.0

样例 3

输入

2 3
HHH
HHT

输出

7.0