타자기 원숭이

여러분의 출판사는 위대한 문학 작품을 쓰기 위해 원숭이들이 키보드를 무작위로 두드리게 하기로 했다. 여러분은 K개의 키가 있는 키보드를 사용하는 원숭이 한 마리의 감독자이며, 각 키에는 영어 대문자가 하나씩 표시되어 있다. (같은 글자가 표시된 키가 여러 개 있을 수도 있다.) 원숭이는 빈 문자열에서 시작하여 다음 과정을 S번 반복한다. 키보드의 키 하나를 균등한 확률로 무작위 선택하여 누르고, 그 키의 글자 하나를 문자열의 오른쪽 끝에 추가한다. 최종적으로 만들어지는 문자열의 길이는 S이다.

여러분은 원숭이가 입력하기를 바라는 길이 L의 목표 단어를 가지고 있다. (목표 단어가 실제 영어 단어일 필요는 없다.) 이 목표 단어는 원숭이가 입력한 내용에 여러 번 나타날 수도 있다. (서로 겹치는 경우도 센다. 예를 들어 목표 단어가 "ABA"이고 원숭이가 "ABABA"을 입력했다면, 여기에는 목표 단어가 두 번 나타난다.)

원숭이가 입력한 목표 단어의 각 등장마다 바나나 하나를 지급할 계획이다. 원숭이의 작업을 검사하러 갈 때, 원숭이가 무엇을 입력했든 지급할 바나나가 항상 충분하도록 필요한 최소 개수의 바나나를 가져간다. 그런 다음 원숭이가 실제로 입력한 목표 단어의 각 등장마다 바나나 하나를 지급한다. 가져간 바나나 중 남은 것은 여러분이 갖는다.

여러분이 갖게 될 바나나 개수의 기댓값은 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트

시간 제한: 240초. 1 ≤ K ≤ 7. 1 ≤ L ≤ S ≤ 7.

큰 데이터 세트

시간 제한: 480초. 1 ≤ K ≤ 100. 1 ≤ L ≤ S ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 줄로 구성된다. 첫 번째 줄에는 공백으로 구분된 세 양의 정수 K, L, S가 주어진다. 두 번째 줄에는 원숭이의 키보드를 나타내는 K개의 영어 대문자로 이루어진 문자열이 주어진다. 세 번째 줄에는 목표 단어를 나타내는 L개의 영어 대문자로 이루어진 문자열이 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 y는 원숭이에게 바나나를 지급한 후 여러분이 갖게 될 바나나 개수의 기댓값이다.

y가 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참고하라.

케이스 #5은 작은 데이터 세트의 제한에 포함되지 않는다는 점에 유의하라.

케이스 #1에서 원숭이는 목표 단어 "MONKEY"을 단 한 번도 입력할 가능성이 없다(키보드에 "MONKEY"의 글자 대부분이 없기 때문이다). 따라서 방문할 때 바나나를 하나도 가져가지 않으며, 물론 하나도 지급하지 않는다. 불쌍한 원숭이!

케이스 #2에서 원숭이는 반드시 "AAAA"을 입력하며, 여기에는 목표 단어 "AAA"이 서로 겹치게 두 번 나타난다. 바나나 두 개를 가져가서 둘 다 지급한다.

케이스 #3에서 원숭이는 다음 결과를 동일한 확률(각각 1/4)로 만든다: "AA", "AB", "BA", "BB". 이들에는 목표 단어가 각각 0, 1, 1, 2번 나타난다. "BB"인 경우에 대비하려면 바나나 2개를 가져가야 하지만, 평균적으로는 (0 + 1 + 1 + 2) / 4 = 1개를 지급한다.

케이스 #4에서 원숭이는 첫 번째로 "G"을 입력할 확률이 1/3이고, 두 번째로 "O"을 입력할 확률이 1/3이므로, "GO"을 입력할 확률은 1/9이다. 바나나 하나를 가져가며, 1/9의 경우에 그것을 지급한다.

케이스 #5에서 원숭이는 이론상 "ROSENCRANTZ"을 최대 아홉 번 입력할 수 있지만, 이것이 단 한 번이라도 일어날 확률은 매우 작아서 답에 허용되는 오차 범위에 비하면 무시할 수 있다.