405409: GYM101954 D Numbers Generator

Among the most popular games in Binary casino is a game called "The Binary Generator". It is played by multiple players and with a single coin. Each player first chooses a sequence of heads and tails of a given length. After that, players or the casino start flipping the coin and the winner is the player whose sequence first appears as a contiguous subsequence of the flip results.

You believe all sequences chosen by players are equally good and so the choice of the sequence does not matter. However, after losing all of your money, you became somewhat doubtful of that. Write a program to prove you wrong. For a given list of sequences of heads and tails of the same length, write the expected number of coin flips which have to be performed until one of the players' chosen sequences appears as a contiguous subsequence in the flip sequence. The expected number of coin flips is the average length of a flip sequence over all possible flip sequences resulting in some player's victory, where each flip sequence is weighted by its probability.

The first line of input contains two integers $$$W$$$ and $$$B$$$ ($$$1 \le W \le 10$$$, $$$1 \le B \le 30$$$), the number of players' sequences and the length of players' sequences, respectively. Next, $$$W$$$ lines follow, each consisting of a sequence of $$$B$$$ letters. Each letter is either "H" for heads or "T" for tails.

Output a single number ­– the expected number of flips. The output will be considered correct if its relative error does not exceed $$$10^{-6}$$$.

1 1
H

2.00000

2 3
HHT
THT

5.00000

2 3
HHH
HHT

7.00000