확률의 역설

공정한 동전을 계속 던진다. 한 번 던질 때마다 앞면 H 또는 뒷면 T가 나오고 각각의 확률은 $1/2$이다. 길이가 같은 결과열은 모두 확률이 같아서, 길이 3인 HHH나 THH는 둘 다 확률이 $1/8$이다.

이제 두 사람이 겨루는 다음 게임을 보자. 두 사람은 길이가 같고 서로 다른 패턴을 하나씩 고른다. 첫 번째 사람이 HHH를, 두 번째 사람이 THH를 고르는 식이다. 그런 다음 같은 동전을 계속 던지면서 함께 지켜보고, 자기 패턴이 먼저 나타난 사람이 이긴다. 던진 결과가 HHTHTTHH로 시작하면 마지막 세 번이 THH이므로 두 번째 사람이 이긴다.

궁금한 것은 두 패턴이 주어졌을 때 첫 번째 사람이 이길 확률이다. 동전이 공정하므로 패턴은 상관없고 두 사람이 $1/2$씩 나눠 가진다고 생각하기 쉽지만 실제로는 그렇지 않다. 이 현상을 확률의 역설이라고 부른다.

확률이 정확히 $1/2$인 짝도 있다. TT와 HH는 대칭이라서 어느 쪽이 먼저 나올 확률이든 같다.

처음 예로 돌아가 첫 번째 사람이 HHH, 두 번째 사람이 THH를 고른 경우를 보자. 이 짝에서 첫 번째 사람이 이기려면 처음 세 번이 모두 H여야 한다. 가장 이른 HHH가 맨 앞에서 시작하지 않았다고 하면 그 바로 앞에 던진 결과가 있고, 전체 모양은 ...?HHH가 된다. ?는 H일 수 없다. H라면 ...HHHH가 되어 한 칸 앞에서 이미 HHH가 완성되고 게임이 그때 끝났을 것이다. T일 수도 없다. T라면 ...THHH가 되어 그 안의 THH가 먼저 완성되므로 두 번째 사람이 이미 이겼을 것이다. 따라서 HHH 대 THH에서는 처음 세 번이 모두 H일 때만 첫 번째 사람이 이기고, 그 확률은 $1/8$이다.

예를 하나 더 들면, 첫 번째 사람이 TTH를 고르고 두 번째 사람이 THH를 고르면 첫 번째 사람이 이길 확률은 $2/3$이다. 이런 확률을 계산하는 프로그램을 작성하라.

입력은 한 줄에 하나씩 주어지는 데이터 여러 개로 이루어진다. 각 줄에는 문자 H와 T로만 이루어지고 길이가 같으면서 서로 다른 패턴 두 개가 공백 하나를 사이에 두고 주어진다. 공통 길이는 1 이상 9 이하이다. 마지막 줄에는 $ 하나만 주어진다.

각 데이터마다 공정한 동전 던지기 결과열에서 첫 번째 패턴이 두 번째 패턴보다 먼저 나타날 정확한 확률을 한 줄에 하나씩 출력한다. 확률은 기약분수로 쓰고 분자와 분모 사이에 /를 넣는다. 두 사람 모두 이길 가능성이 0이 아니므로 이 값은 항상 0보다 크고 1보다 작다.

주의: 최종 확률의 분자와 분모는 모두 32비트 정수로 나타낼 수 있다. 다만 풀이에 따라 중간 계산에서 64비트 정수(Java의 long, C++의 long long)가 필요할 수 있고, 그때도 넘침에 주의해야 한다.