I와 l

알파벳의 대소문자 중에서 대문자 I와 소문자 l은 글꼴에 따라 모양이 비슷해서 잘 구분되지 않기도 한다. 이는 때때로 유머의 소재가 되는데, 예를 들어 2020년 3월 28일에 열린 구데기컵의 3개 디비전 중 5시간짜리 디비전의 이름인 "진짜 최종 구데기컵: ReguIar Division"에서 ReguIar의 다섯 번째 글자는 소문자 l이 아니라 대문자 I였다. 문제 지문의 기본 폰트에서는 I와 l을 구분하는 방법이 길이다. 두 문자를 붙여 놓은 Il을 보면 l이 I보다 조금 더 길다는 것을 알 수 있다. 하지만 이렇게 구분할 수 있다 해도 IlIllIIllI와 같은 문자열을 기억하는 데는 많은 시간이 걸린다. 그래서 자기 아이디를 쉽게 노출하고 싶지 않은 사람들은 I와 l을 적절히 섞어 아이디를 만들기도 한다.

I와 l로 된 아이디를 관찰하던 실버는 문득 이런 문자열들의 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 길이의 기댓값이 얼마일지 궁금해졌다. 최장 공통 부분 수열은 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 수열이다. 문자열 $X, Y$에 대해 $X$와 $Y$의 LCS 길이를 $LCS(X, Y)$라 하자. 길이 $n$인 문자열 $S$가 주어졌을 때, I와 l로 이루어진 길이 $m$인 문자열들의 집합(regex 기준 [Il]{m})에서 임의로 뽑은 문자열 $T$에 대해 $LCS(S, T)$의 기댓값을 구해야 한다.

첫 번째 줄에 $n, m$이 주어진다.

두 번째 줄에 I와 l로만 이루어진 길이 $n$의 문자열 $S$가 주어진다.

첫 번째 줄에 문제의 정답을 기약분수 a/b 형태로 출력한다.

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