Expected Tosses for a Target Sequence

You are given a coin which, when tossed, shows head (H) with probability \(\frac{a}{b}\) and tail (T) with probability \(1-\frac{a}{b}\). You are also given a target sequence consisting of characters 'H' and 'T'. Your task is to determine the expected number of tosses needed until the target sequence appears for the first time.

Note that if the target sequence contains a character which has zero probability of occurring (for example, if the sequence has an 'H' but \(a=0\), or a 'T' but \(a=b\)), then the target sequence is impossible to achieve and you should output -1.

The classical example: when \(a=1, b=2\) (i.e. a fair coin) and the target sequence is HT, one can argue by conditioning that the expected tosses is 4. (Explanation: If the first toss is T, you are effectively starting over; if the toss is H, you only need an extra toss to get T, and the expected extra toss for T is 2 in a fair coin.)

In the general case, you must consider biases and overlapping occurrences of the sequence. A standard approach is to build an automaton (using for instance the KMP algorithm) representing the maximal prefix which is also a suffix and then set up a system of linear equations:

[ E[i] = 1 + \begin{cases}\frac{a}{b}E[\text{next}(i, H)] + \Bigl(1-\frac{a}{b}\Bigr)E[\text{next}(i, T)] & \text{for }0 \le i < m,\ E[m] = 0, \quad\text{(absorbing state)} \end{cases} ]

Solve the system, and the answer will be \(E[0]\), the expected tosses from the beginning.

inputFormat

The input consists of two lines:

• The first line contains two integers \(a\) and \(b\) (with \(0 \le a \le b\) and \(b>0\)), representing the probability \(\frac{a}{b}\) for head.
• The second line is a non-empty string representing the target sequence, consisting only of characters 'H' and 'T'.

outputFormat

If it is possible for the target sequence to appear, output the expected number of tosses with a precision of at least 6 decimal places. Otherwise, if the target sequence is impossible, output -1.

sample

1 2
HT

4.000000