제네릭 포커

$N \times M$장의 카드로 이루어진 덱이 있습니다. 각 카드에는 랭크가 하나 적혀 있으며, 랭크는 $1$부터 $M$까지의 정수입니다. 덱에는 각 랭크마다 정확히 $N$장의 카드가 들어 있습니다. 여기서는 랭크가 $m$인 카드를 간단히 $m$으로 표기합니다.

덱에서 무작위로 $L$장의 카드를 뽑아 하나의 핸드를 만듭니다. 뽑힌 핸드가 주어진 패턴과 일치하면 보너스를 받습니다. 패턴의 문법은 다음과 같습니다.

hand_pattern = card_pattern1 ' ' card_pattern2 ' ' ... ' ' card_patternL
card_pattern = '*' | var_plus
var_plus = variable | var_plus '+'
variable = 'a' | 'b' | 'c'

• hand_pattern: 핸드의 서로 다른 카드들을 패턴의 각 card_pattern에 일대일로 대응시켜 모든 card_pattern이 자신에게 대응된 카드와 일치할 수 있으면, 그 핸드는 hand_pattern과 일치합니다.
• card_pattern
  • card_pattern이 별표 *이면 임의의 카드와 일치합니다.
  • 문자 a, b, c는 변수이며, 같은 변수의 모든 등장은 같은 랭크의 카드와 일치해야 합니다. 변수 뒤에 더하기 기호 +가 붙으면, 그 card_pattern은 (해당 변수에 대응된 랭크) + (더하기 기호의 개수)에 해당하는 랭크의 카드와 일치합니다.
  • 어떤 변수 뒤에 $k$개의 +가 붙은 card_pattern이 패턴에 등장하면, 같은 변수에 대해 $0$개부터 $k-1$개까지의 +가 붙은 card_pattern도 모두 패턴에 등장한다고 가정할 수 있습니다. 예를 들어 a+++가 등장하면 a, a+, a++도 함께 등장합니다.

서로 다른 변수가 어떤 랭크를 뜻하는지에 대한 제약은 없습니다. 예를 들어 a와 b는 같은 랭크의 카드와 일치할 수도 있고, 그렇지 않을 수도 있습니다.

몇 가지 예를 봅시다. 패턴

a * b a b

은 다음 핸드와 일치합니다. 이때 a와 b는 각각 $3$과 $10$을 (또는 $10$과 $3$을) 뜻합니다.

3 3 10 10 9

같은 패턴은 다음 핸드와도 일치하며, 이 경우 a와 b는 모두 $3$을 뜻합니다.

3 3 3 3 9

패턴

a a+ a++ a+++ a++++

는 다음 핸드와 일치하며, 이때 a는 $4$를 뜻합니다.

4 5 6 7 8

주어진 hand_pattern에 대해, 덱에서 무작위로 뽑은 핸드가 그 패턴과 일치할 확률을 구하는 프로그램을 작성하세요.

입력은 여러 개의 데이터셋으로 이루어져 있습니다. 각 데이터셋의 형식은 다음과 같습니다.

N M L
card_pattern1 card_pattern2 ... card_patternL

첫 번째 줄에는 세 양의 정수 $N$, $M$, $L$이 주어집니다. $N$은 각 랭크의 카드 장수, $M$은 랭크의 개수, $L$은 한 핸드의 카드 장수입니다. 제약 조건은 다음과 같습니다.

• $1 \le N \le 7$
• $1 \le M \le 60$
• $1 \le L \le 7$
• $L \le N \times M$

두 번째 줄에는 $L$개의 card_pattern으로 이루어진 hand_pattern이 공백으로 구분되어 주어집니다.

입력의 끝은 공백으로 구분된 세 개의 $0$(0 0 0)만 있는 줄로 표시됩니다. 이 줄은 처리하지 않습니다.

각 데이터셋마다, 핸드가 hand_pattern과 일치할 확률을 기약분수 $p/q$ 형태로 한 줄에 출력하세요. 여기서 $q \ge 1$이고 $\gcd(p, q) = 1$입니다. 확률이 $0$이면 0/1을, 확률이 $1$이면 1/1을 출력합니다. 각 줄에는 이 분수 외의 다른 문자를 포함하지 마세요.