타자기 앞의 원숭이들

충분히 많은 원숭이를 타자기 앞에 앉혀 두고 충분히 오랫동안 아무 키나 치게 하면 언젠가는 셰익스피어의 모든 작품을 그대로 쳐낼 것이라는 이야기를 들어 본 적이 있을 것이다. 각 원숭이가 완전히 무작위로 키를 누른다고 가정하는 이야기다.

여기서는 이와 관련된 문제를 푼다. 원숭이는 키를 무작위로 누르다가 처음으로 스페이스바를 누르는 순간 멈춘다. 매 타건은 서로 독립이며, 원숭이는 주어진 확률에 따라 특정 소문자를 누르거나 확률 $s$로 스페이스바를 누른다. 이 확률들을 모두 합하면 $1$이 된다. 처음 스페이스바를 누르기 전까지 친 소문자들의 나열이 원숭이가 만들어 낸 단어이며, 이 나열이 어떤 단어와 정확히 일치할 때 원숭이가 그 단어를 쳤다고 한다.

서로 다른 소문자 단어들의 목록이 주어질 때, 원숭이가 그중 하나를 우연히 쳐낼 확률을 구하라.

첫 번째 줄에는 데이터 집합의 개수 $K$가 주어진다. 각 데이터 집합은 다음과 같은 형식을 가진다.

첫 줄에는 세 값 $n$, $m$, $s$가 주어진다 ($1 \le n \le 100$, $1 \le m \le 26$, $0 \le s \le 1$). $n$은 목표 단어의 개수, $m$은 타자기의 글자 키 개수, $s$는 스페이스바를 누를 확률이다.

이어지는 $m$개의 줄에는 각각 소문자 하나와 실수 하나가 주어지며, 이는 그 글자를 누를 확률이다. 이 확률들과 $s$를 모두 합하면 $1$이 된다.

그다음 $n$개의 줄에는 각각 단어 $w_i$가 하나씩 주어진다. 각 단어는 타자기에 있는 소문자들로만 이루어지며 길이는 $1$자 이상 $20$자 이하이다. 한 데이터 집합 안의 단어들은 모두 서로 다르다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호이며 $1$부터 시작한다. 다음 줄에는 원숭이가 주어진 단어 중 적어도 하나를 칠 확률을 출력한다.

이 확률은 매우 작을 수 있으므로, 가수부 소수점 아래 정확히 네 자리와 부호가 붙은 두 자리 이상의 지수를 가지는 과학적 표기법으로 출력한다. 예를 들면 3.7602E-13 또는 0.0000E+00과 같다.

연속한 두 데이터 집합 사이에는 빈 줄을 하나 넣는다.