타자기 원숭이

당신이 다니는 출판사는 원숭이에게 키보드를 무작위로 두드리게 해서 위대한 문학 작품을 쓰기로 했다. 당신은 원숭이 한 마리를 맡았다. 이 원숭이의 키보드에는 키가 $K$개 있고, 각 키에는 영어 대문자가 하나씩 적혀 있다. 같은 글자가 적힌 키가 여러 개 있을 수도 있다.

원숭이는 빈 문자열에서 시작해서 다음 동작을 $S$번 반복한다. 키보드의 키 하나를 균등한 확률로 무작위로 골라 누르고, 그 키의 글자를 문자열의 오른쪽 끝에 덧붙인다. 그래서 최종 문자열의 길이는 $S$가 된다.

당신에게는 원숭이가 쳐 주기를 바라는 길이 $L$짜리 목표 단어가 있다. 목표 단어가 실제로 존재하는 영어 단어일 필요는 없다. 목표 단어는 원숭이가 친 문자열 안에 여러 번 나타날 수도 있고, 겹쳐서 나타난 것도 각각 센다. 예를 들어 목표 단어가 "ABA"이고 원숭이가 "ABABA"를 쳤다면 목표 단어는 두 번 나타난 것이다.

당신은 목표 단어가 나타난 횟수만큼, 한 번에 바나나 하나씩 원숭이에게 준다. 원숭이의 결과물을 보러 갈 때는 원숭이가 무엇을 쳤든 삯을 다 치를 수 있는 최소 개수의 바나나를 가져간다. 그리고 실제로 나타난 횟수만큼 바나나를 주고, 남은 바나나는 당신이 가진다.

당신이 가지게 되는 바나나 개수의 기댓값을 구하라.

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

제한

• $1 \le T \le 100$
• $1 \le K \le 100$
• $1 \le L \le S \le 100$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호이고, $y$는 원숭이에게 삯을 주고 남는 바나나 개수의 기댓값이다.

$y$는 소수점 아래 여섯째 자리까지 출력한다. 일곱째 자리에서 반올림하고, 값이 정확히 절반이면 올린다.

첫 번째 케이스에서는 키보드 BANANAS에 MONKEY의 글자가 대부분 없으므로 원숭이가 목표 단어를 칠 가망이 전혀 없다. 바나나를 가져가지도, 주지도 않는다.

두 번째 케이스에서 원숭이는 반드시 AAAA를 치고, 그 안에는 AAA가 겹쳐서 두 번 나타난다. 바나나 두 개를 가져가서 둘 다 준다.

세 번째 케이스에서 원숭이는 AA, AB, BA, BB를 각각 확률 $1/4$로 치고, 목표 단어는 각각 0번, 1번, 1번, 2번 나타난다. BB에 대비해 바나나 두 개를 가져가야 하지만, 평균적으로 주는 개수는 $(0 + 1 + 1 + 2) / 4 = 1$이다.

네 번째 케이스에서 첫 글자가 G일 확률이 $1/3$, 둘째 글자가 O일 확률이 $1/3$이므로 GO를 칠 확률은 $1/9$이다. 바나나 하나를 가져가서 $1/9$의 확률로 내준다.

다섯 번째 케이스에서 원숭이는 이론적으로 ROSENCRANTZ를 아홉 번까지 칠 수 있지만, 그 확률은 너무 작아서 소수점 아래 여섯째 자리에 드러나지 않는다.