Description

There is a coin, with the probability of getting heads H being $\frac{a}{b}$, and the probability of getting tails T being $1-\frac{a}{b}$. Now TT starts playing a coin-tossing game and records each result: heads as H and tails as T. Thus she obtains a coin-toss sequence like HTHHT…. She suddenly wonders: when both probabilities of heads and tails are $\frac{1}{2}$, what is the expected number of tosses needed for the sequence to contain the target sequence HT. However, after thinking for $1$ second, she realizes that if the first toss is T, then she still expects to need the number of tosses to obtain HT; if the first toss is H, then she only needs the expected number of tosses to obtain T, which is clearly $2$. Let $x$ be the expected number of tosses to obtain HT, then we have:

$$x=1+\left(\frac{1}{2}\times x+\frac{1}{2}\times 2\right)$$

Solving gives $x=4$, so the expected number of tosses to obtain HT is $4$.

After solving this much simpler problem, she begins to think about the general case, where the probabilities of heads and tails are not necessarily equal, and the target sequence is not necessarily HT. However, after a long time of hard thinking, she still gets nowhere, so she turns to you for help.

Input Format

The first line contains two numbers $a, b$, as defined in the description.

The next line contains a string $S$ consisting only of H and T, representing the target sequence to obtain.

Output Format

Output a single line $\frac{p}{q}$, where $p$ and $q$ are positive integers and are coprime, representing the expected number of tosses needed to obtain the target sequence $S$.

Note that if $q$ is $1$, do not omit /1.

1 2
HT

4/1

Hint

For $50\%$ of the testdata, $a=1, b=2, |S|\le 20$.

For $100\%$ of the testdata, $a<b, b\le 100, |S|\le 1000$.

Translated by ChatGPT 5