사교 댄서

지역 사교 댄스 교실은 새로운 사람을 만나는 좋은 방법이다. 일반적인 입문 사교 댄스 수업은 다양한 춤을 다루지만, 모두 몇 가지 기본적인 구조적 요소를 공통으로 가진다. 대부분의 사교 댄스는 리드 한 명과 팔로우 한 명, 두 사람을 기준으로 한다.

지역 사교 댄스 클럽은 학생들에게 스윙, 컨트리, 바차타 세 가지 춤을 가르친다. 학기 말 파티에서 각 학생은 이 세 춤 중 일부를 알게 된다. 강사들은 학생들을 긴장시키기 위해 세 장르의 음악을 모두 틀어 준다. 학생들은 훈련이 잘 되어 있어, 어떤 노래가 나오는지에 따라 어떤 춤을 춰야 하는지 즉시 안다.

리드가 팔로우에게 춤을 청하면 두 사람은 서로가 아는 춤을 비교한다. 노래가 나올 때 리드와 팔로우 한 쌍이 하는 행동은 세 가지 경우로 나뉜다.

1. 둘 다 이 노래에 맞춰 추는 법을 안다. 둘은 춤을 춘다.
2. 둘 다 이 노래에 맞춰 추는 법을 모른다. 둘은 빠지고 즐겁게 대화를 나눈다.
3. 정확히 한 명만 이 노래에 맞춰 추는 법을 안다. 모르는 사람은 새빨개져서 당황하고 허둥대다가 댄스홀 밖으로 달려 나가고, 나가다가 케이블에 걸려 넘어져 촛불을 쓰러뜨려 댄스홀이 불에 탄다.

세 번째 경우는 다소 과장이지만, 학생들은 정확히 한 명만 아는 노래가 나올 가능성이 조금이라도 있으면 짝을 이루지 않는다.

학생들이 짝을 이룬 뒤, 학교는 $M$곡을 튼다. 모든 학생이 짝을 이룰 필요는 없다. 일부는 빠져서 화재 감시를 할 수도 있다. 각 노래는 스윙, 컨트리, 바차타 중 하나로 균등하고 독립적으로 무작위 선택된다.

학생들은 모두 가능한 한 많은 춤을 추고 싶어 한다. 총 춤의 수는 각 노래마다 춤을 추는 리드-팔로우 쌍의 수의 합이다. 학생들이 최적으로 짝을 이루고, 노래의 장르가 독립적으로 무작위 선택될 때, 파티가 진행되는 동안 발생하는 춤의 기대값은 얼마인가?

첫 줄에 세 정수 $L$, $F$, $M$이 주어지며, 각각 리드의 수, 팔로우의 수, 댄스홀에서 재생하는 곡의 수이다. $L + F \leq 10^5$, $1 \leq M \leq 10^{12}$. 이어서 각 리드에 대해 $L$줄이 주어진다. 각 줄은 리드가 아는 춤의 수 $k (1 \leq k \leq 3)$로 시작하고, 그 뒤에 해당 춤의 이름이 이어진다. 각 춤 이름은 "swing", "country", "bachata" 중 하나이다. 각 춤 스타일은 한 댄서에게 최대 한 번만 나타난다. 이어서 같은 형식으로 팔로우를 설명하는 $F$줄이 주어진다.

발생하는 춤의 기대값을 나타내는 실수 하나를 출력한다. 절대 오차 또는 상대 오차가 $10^{-5}$ 이하이면 정답으로 인정된다.