I and l

Among the uppercase and lowercase letters of the alphabet, the uppercase I and the lowercase l look similar in some fonts and are hard to tell apart. This is sometimes used as material for jokes; for example, in the name "진짜 최종 구데기컵: ReguIar Division" of the 5-hour division among the three divisions of the Gudegi Cup held on March 28, 2020, the fifth character of ReguIar was the uppercase I, not the lowercase l. In the default font of problem statements, the way to tell I and l apart is length. Looking at Il, the two characters placed side by side, you can see that l is slightly longer than I. Even if you can tell them apart this way, remembering a string like IlIllIIllI takes a lot of time. So people who do not want their IDs to be easily exposed sometimes make IDs by mixing I and l appropriately.

Silver, who had been observing IDs made of I and l, suddenly wondered what the expected value of the LCS (Longest Common Subsequence) length of such strings would be. A longest common subsequence is the longest sequence that is a subsequence of both sequences. For strings $X, Y$, let the length of the LCS of $X$ and $Y$ be $LCS(X, Y)$. Given a string $S$ of length $n$, you must find the expected value of $LCS(S, T)$ for a string $T$ drawn uniformly at random from the set of strings of length $m$ made of I and l (in regex terms, [Il]{m}).

The first line gives $n, m$.

The second line gives a string $S$ of length $n$ made only of I and l.

On the first line, print the answer to the problem in the form of the irreducible fraction a/b.

• $1 \le n \le 20$
• $1 \le m \le 50$